전체 글1321 [백준] 1309 동물원 - Dynamic Programming / Java • 문제 링크 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net • 풀이 과정 n칸 마다 두 개의 방이 존재하고, 사자들을 배치할 때 가로 또는 세로로 붙어서 배치할 수 없는 조건에 의하여 이전 칸에 사자를 배치하지 않는 경우을 제외하고 이전에 배치된 방에 따라 현재 방의 배치가 결정된다. 배치하는 경우의 수는 3가지로, dp[n][0] 은 두 개의 방 모두 배치하지 않은 경우, dp[n][1] 은 첫 번째 방에 배치한 경우, dp[n][2] 은 두 번째 방에 배치한 경우를 나타낸다. 따라서 2차원 dp배열을 dp[n + 1][3] 의 크기로 생성하고, dp[1][0] = dp[1][1] = dp[1][2] = 1 로 각각의 경우를 초기화한다... 2022. 8. 29. [백준] 1149 RGB거리 - Dynamic Programming / Java • 문제 링크 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net • 풀이 과정 dp 배열을 2차원 배열로 생성하고, 이는 dp[집][색상] 을 의미한다. 이후 각각의 집에 색을 칠하는 비용을 입력받으며, 무조건 첫번째 집에 가장 적은 비용의 색을 칠함에 따라 정답을 구할 수 있는 것이 아니기 때문에 첫번째 집에 3가지 색을 칠한 경우의 수를 모두 구한다. 현재 집까지 색을 칠하는 최소 비용은, 이전 집에서 현재 집과 다른 두 색상 중 적은 비용과 칠할 색의 비용을 합한 값이므로 i번째 집에.. 2022. 8. 28. [백준] 2225 합분해 - Dynamic Programming / Java • 문제 링크 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net • 풀이 과정 dp 배열을 2차원 배열로 생성하고, dp[n + 1][k + 1] 으로 크기를 지정한다. 이때 n = 1 일 때 i 개로 n을 만드려면 각각 i 개의 경우의 수가 존재,(dp[1][i] = i) i 를 k = 1 개로 만드려면 각각 1개의 경우의 수가 존재하므로 해당 값들을 초기화시킨다.(dp[i][1] = 1) 이어서 규칙성을 찾기 위해 n = 1 ~ 3, k = 1 ~ 3 범위의 예시는 아래와 같다. dp[1][1] : 1 (1) dp[1][2] : 2 (1 + 0, 0 + 1) dp[1][3] : 3 (1 + 0 + 0, 0 + 1 + 0, 0 + 0 .. 2022. 8. 27. [백준] 1699 제곱수의 합 - Dynamic Programming / Java • 문제 링크 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net • 풀이 과정 각각의 자연수 n 의 최대 제곱수의 갯수는 n 이므로, 반복문을 통해 제곱수의 최대 개수를 초기화한다.(dp[i] = i) 1 ~ 3 은 제곱수의 최솟값 또한 1 ~ 3 이며, 나머지는 아래와 같이 구할 수 있다. n 제곱수 점화식 개수 dp[4] 2^2 dp[4 - 2^2] + 1 = dp[0] + 1 1 dp[5] 2^2 + 1^2 dp[5 - 2^2] + 1 = dp[1] + 1 2 dp[.. 2022. 8. 26. [백준] 1912 연속합 - Dynamic Programming / Java • 문제 링크 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net • 풀이 과정 입력된 수열의 연속된 수의 합을 구하고(sum), 해당 값과 현재까지 구해진 연속된 수의 합(max) 의 최대값을 비교하여 갱신한다. 이때 합이 음수일 경우,(sum < 0) 다음에 연속된 수의 합은 해당 수보다 작으므로 sum = 0 으로 초기화하여 새로 합을 구한다. 이렇게 최종적으로 갱신된 max 값을 정답으로써 출력한다. • 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWri.. 2022. 8. 25. [백준] 2193 이친수 - Dynamic Programming / Java • 문제 링크 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net • 풀이 과정 [백준] 10844 쉬운 계단 수 - Dynamic Programming / Java • 문제 링크 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net • 풀이 과정 dp 배열을 2차원 배열로 정의하였으며, 이는 dp[자릿수][자릿값] 을 의미한 graycode.tistory.com 위 문제와 유사하게 2차원 dp 배열로 접근하여 풀이한다. 이친수.. 2022. 8. 24. 이전 1 ··· 196 197 198 199 200 201 202 ··· 221 다음
