아이디어 dp[i] 를 최대 i 만큼의 무게를 넣을 수 있는 배낭을 맸을 때 넣을 수 있는 물건들 가치의 최대값이라고 정의를 한다면 물건의 무게가 각각 6 4 3 5 그 가치가 각각 13 8 6 12 일 때 dp[i] 는 dp[i] = max(dp[i - 6] + 13, dp[i - 4] + 8, dp[i - 3] + 6, dp[i - 5] + 12) 라고 볼 수 있다. 다만 이 때 주의해야할 점은 같은 물건을 배낭에 여러 번 담을 수는 없다는 것이다. 예를 들어 dp[3] 을 계산할 때 무게가 3인 물건을 담는 게 가장 가치가 크게 되는 경우이므로 이미 배낭에 담았는데 dp[6] 을 계산할 때 또 담으면 안 된다는 것이다. 이는 각 물건에 대해 dp[i] 를 갱신하는 과정을 i 의 오름차순이 아닌 내림..

아이디어 1. bfs 탐색을 통해 국경이 열리는 국가들을 하나의 연합으로 묶고 2. (연합 총 인구수 / 연합 국가 수) 를 계산하여 연합으로 묶인 국가들의 인구를 갱신해준다. 3. 이 때 기존 인구 수와 갱신해야 하는 인구 수가 같다면 갱신이 불필요 즉 인구 이동이 일어나지 않으므로 인구 갱신 시 '기존 인구 수와 갱신 인구 수가 같지 않을 때만 인구 이동이 일어났다고 판단한다' 매일 새로운 visited 배열과 함께 1 ~ 3 과정을 수행하고 3 과정에서 '인구 이동이 없었다' 라고 판단이 되면 다음 날로 넘어가지 않고 현재까지 며칠이 소요되었는지를 출력하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.In..

아이디어 이 문제는 별다른 아이디어는 필요 없고 문제에서 요구하는 바를 순서에 따라 정확히 구현하기만 하면 되는 문제이다. 노트북에 스티커를 붙이는 과정은 1. 스티커를 붙일 수 있는 가장 왼쪽 상단 위치를 찾는다. 2. 스티커를 붙인다. 3. 만약 붙일 수 있는 위치가 없다면 90도 회전해서 1부터 반복한다. 4. 스티커 회전을 90, 180, 270 도 모두 해봐도 붙일 수 없다면 해당 스티커는 버린다. 따라서 1) 왼쪽 상단 부터 탐색하여 스티커를 붙일 수 있는 가장 왼쪽 상단의 위치를 찾는 메서드 2) 스티커를 붙이는 메서드 3) 스티커를 90도 회전시키는 메서드 이 3가지만 잘 구현해낸다면 해결할 수 있는 문제이다. 풀이코드 import java.io.BufferedReader; import j..

아이디어 (x1, y1) ~ (x2, y2) 까지의 직사각형에 존재하는 값들의 합을 구하기 위해 먼저 (1, 1) 에서 (x, y) 까지의 합을 담고 있는 dp 배열을 만든다. dp[i][j] 를 (1, 1) 에서 (i, j) 까지 만들어지는 직사각형에 존재하는 값들의 합이라고 정의한다면 (x1, y1) ~ (x2, y2) 직사각형에 존재하는 값들의 합은 dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1] 이 된다. (1, 1) 에서 (i, j) 까지 직사각형에 존재하는 값들의 합인 dp[i][j] 에 대한 점화식은 다음과 같이 세울 수 있다. dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j ..

아이디어 이전의 동전 1 문제와 유사한 문제다(https://w-hand.tistory.com/57) dp[i] 를 i 원을 만들기 위해 필요한 최소 동전의 개수라고 정의하고 동전이 1원, 5원, 12원이 있다면 dp[i] = min(dp[i - 1], dp[i - 5], dp[i - 12]) + 1 이 된다. 문제 특성 상 동전의 종류는 입력에 따라 달라지므로 반복문을 사용해서 위의 점화식을 구현해야한다. 그리고 이 때 초기값은 동전 가치의 최대값인 100,000 보다 1 큰 100,001 로 설정한다. (1원짜리 동전으로 100,000 원을 만드는 것이 동전 갯수의 최대 경우이기 때문에 이보다 더 큰 값으로 설정하여 해당 금액을 만들 수 없는 경우를 표현한다) 풀이코드 import java.io.Bu..

아이디어 dp[i] : i 원을 만드는 경우의 수 동전이 1원, 2원, 5원이 있다고 가정하였을 때 단순히 생각해보면 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 5] 다만 이와 같은 계산 방식은 '사용한 동전의 구성이 같은데, 순서만 다른 것'을 다르게 바라보는 방식이므로 약간의 변형이 필요하다. 위와 같은 방식으로 계산하면 3원을 만드는 방법에는 1) 1 + 1 + 1 2) 1 + 2 3) 2 + 1 3가지가 존재하게 되는데 문제에서 요구하는 바에 따르면 2) 와 3)은 같은 경우로 바라봐야 하므로 1) 1 + 1 + 1 2) 1 + 2 만이 계산될 수 있도록 해야한다. 이는 1원짜리 동전으로 i 원을 먼저 만들고 그 후 2원짜리 동전을 추가하여 i 원을 만들 수 있는 경우의..

아이디어 i 번째 스위치를 누를 것인가 말 것인가는 i - 1번째 전구의 상태가 어떤가에 따라 결정된다. i - 1 번째 전구의 상태가 만들고자 하는 전구의 상태와 동일하다면 i 번째 스위치를 누르면 안 되고 i - 1 번째 전구의 상태가 만들고자 하는 전구의 상태와 다르다면 i 번째 스위치를 눌러야 한다. 다만 가장 첫 번째 전구는 i - 1 번째 전구가 없기 때문에 가장 첫 번째 전구의 스위치를 누르지 않고 시작하는 케이스와 누르고 시작하는 케이스를 구분하여 2 가지 케이스에 대해 위의 규칙을 적용한다. 마지막 전구의 스위치까지 결정짓고 난 후에는 가장 마지막 전구의 상태가 만들고자 하는 전구의 상태와 동일한지 확인하여 가장 최소 회수를 구하면 된다 ※ 0 ~ N -2 번째까지의 전구를 확인하지 않는..

아이디어 N 행 M 열의 표 A 에서 임의의 i, j 좌표를 기준으로 가로 방향 공차와 세로 방향 공차를 설정해서 숫자를 만들고 해당 숫자가 완전제곱수인 경우 이전의 결과값과 비교해가며 더 큰 수로 갱신하는 방법을 사용하면 된다. 이 때 공차는 음수도 가능하기 때문에 가로 방향 공차와 세로 방향 공차의 범위는 아래와 같다. 세로 방향 공차 : -N < d1 < N 가로 방향 공차 : -M < d2 < M 숫자 하나를 택하고 여기에 다음 숫자를 택해서 이어 붙이는 것은 (이전 숫자 * 10 + 다음 숫자) 식을 이용하면 된다. 완전제곱수인지 여부는 해당 숫자의 제곱근을 int 타입으로 변환했을 때 값이 그대로인지를 체크하는 것을 통해 알 수 있다. 풀이코드 import java.io.BufferedRead..