Koder / 박성훈
article thumbnail
백준 BOJ 17619 - 개구리 점프
알고리즘/백준 BOJ 2023. 8. 1. 01:32

https://www.acmicpc.net/problem/17619 17619번: 개구리 점프 첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 < x2) 모든 www.acmicpc.net 스위핑 + 유니온파인드 문제 X 좌표가 서로 일부 겹치고 있다면 모종의 방법을 통해서 점프해 이동할 수 있기 때문에, 문제의 입력으로 들어오는 Y좌표와 지문의 조건 점프할 때 다른 통나무 위를 지나면 안된다. 를 무시할 수 있다. 이를 무시하고 x좌표만을 사용한 수직선들로 보면 겹치는 부분이 있는 선분들에 대해서 같은 그룹으로 묶어줘야 함을 알 수 있고,..

article thumbnail
백준 BOJ 3649 - 로봇 프로젝트
알고리즘/백준 BOJ 2023. 8. 1. 01:27

https://www.acmicpc.net/problem/3649 3649번: 로봇 프로젝트 각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에 www.acmicpc.net 이분탐색 문제 std::unordered_map 쓰면 날로먹을수있을거같이 생겨먹었는데 왠지 모를 이유로 잘 안풀려서 이분탐색으로 해결했다. 둘의 합이 X*10000000 = K 가 되게 해야하기 때문에, 어떤 한 수를 정해줬다면 해당 수와 더해서 K가 되게끔 하는 수를 O(logN) 시간에 찾아야 한다. 찾아내는 가장 좋은 방법은 이분탐색. 이때, 어떤 한 수 a가 한개밖..

article thumbnail
백준 BOJ 1208 - 부분수열의 합 2
알고리즘/백준 BOJ 2023. 8. 1. 01:17

boj 1182 부분수열의 합 에서 범위를 두배로 키운 문제. https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 밋인더 미들 알고리즘을 사용한다. boj 1182에서와 같이, N이 20일때는 모든 경우에 대해서 브루트포싱할때 전체 연산 횟수가 백만 정도여서 깔끔하게 해결이 가능하지만, N이 40인 이 문제에서는 전체 연산 횟수도 백만의 제곱이어서 시간초과를 받게 된다. 시간초과를 방지하기 위해 입력으로 들어..

article thumbnail
백준 BOJ 11058 - 크리보드
알고리즘/백준 BOJ 2023. 7. 30. 22:22

https://www.acmicpc.net/problem/11058 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net DP 문제. DP[i] 를 버튼을 i번 눌러서 화면에 출력할 수 있는 A 개수의 최댓값으로 만든다. DP[i] 의 기초 값은 DP[i-1] + 1 이다. ( 1번 버튼 화면에 A를 출력한다를 사용 ) 2, 3, 4번 연산은 사실상 한 세트라고 생각하면 되는데, 어..

article thumbnail
백준 BOJ 19539 - 사과나무
알고리즘/백준 BOJ 2023. 7. 30. 21:57

https://www.acmicpc.net/problem/19539 19539번: 사과나무 첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다. www.acmicpc.net 굉장히 빠르게 풀어내서 만족스러운 문제. 일단 쉽게 관찰할 수 있는 첫번째 특징으로, 입력으로 들어온 $h_k$ 들의 합 $sum$ 이 반드시 3의 배수여야만 한다. 두 물뿌리개를 동시에 사용하면 물이 3만큼 뿌려지게 되기 때문이다. 예제 입력 4로 설명해주고 있는 또다른 조건의 하나로, 이 조건으로 인해 골드5라는 티어를 배정받지 않았나 싶다. 나무 하나를 2만큼 성장시키는 물뿌리개는 아무리 뿌려도 짝수 높이만큼의 나무를 만들 수 있기 때..

article thumbnail
백준 BOJ 2643 - 색종이 올려 놓기
알고리즘/백준 BOJ 2023. 7. 30. 21:46

https://www.acmicpc.net/problem/2643 2643번: 색종이 올려 놓기 첫 번째 줄에는 색종이의 장수가 주어진다. 다음 줄부터 각 줄에 색종이의 두 변의 길이가 주어진다. 두 변의 길이는 한 칸 띄어 주어진다. 색종이의 최대 장수는 100이고, 각 변의 길이는 1000보다 www.acmicpc.net DP 문제. DP[i] 를 i번 색종이를 제일 위에 쌓을때 최대 장수로 정의한다. dp[i]를 구하는 방법은 i번 색종이 밑에 놓일 수 있는 보다 큰 색종이 k에 대한 dp[k] 와 비교를 해서, dp[i] = max(dp[i], dp[k]+1) 식으로 계산해주면 된다. 이때, k를 보다 빨리 찾고 편하게 비교하기 위해서, 입력으로 받는 색종이를 일괄적으로 가로 / 세로로 방향을 고..

반응형