DP (7) 썸네일형 리스트형 [백준] 1932번: 정수 삼각형 - JAVA 🔗 문제 링크 BOJ 1932번: 정수 삼각형 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 📝 풀이 과정 위층부터 차례로 누적하며 아래층으로 내려왔을 때, 가장 최대가 되는 수의 합을 구하는 문제이다. 문제대로 해결하는 방법도 있겠지만, 그렇게 되면 제일 마지막 층의 합을 구했을 때 다시 한 번 반복을 돌며 최대값을 찾아야 된다고 생각했다. 이를 반대로 아래에서 위로가며 최대값을 누적하는 방식으로 답을 구했다. for (int i = N - 1; i > 0; i--) { for (int j = 0; j < i; j++) nums[i-1][j] += Math.max(nums[i].. [백준] 1149번: RGB거리 - JAVA 🔗 문제 링크 BOJ 1149번: RGB거리 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 📝 풀이 과정 만약, N번 집의 색이 빨간색이라면, N + 1의 집의 색깔은 초록색이나 파란색으로 칠하는 경우밖에 존재하지 않는다. 다시 말하면 N번 집의 색이 빨간색이라면 N - 1의 집의 색은 초록색이나 파란색이라는 의미가 된다. 따라서, i번째에서 가장 적은 비용으로 빨간색을 칠하는 경우는 $dp[i][0] = Min(dp[i-1][1], dp[i-1][2]) + cost[i][0]$가 되고.. [백준] 11727번: 2×n 타일링 2 - JAVA 🔗 문제 링크 BOJ 11727번: 2×n 타일링 2 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 📝 풀이 과정 [백준] 11726번: 2×n 타일링 - JAVA과 이어지는 문제이다. 노란색으로 체크된 n - 1의 타일에 2x1 타일이 세로로 하나 붙은 형태를 가지고 있고, 파란색으로 체크된 n - 2의 타일에 2x1 타일이 가로로 2개 붙어있거나, 2x2 타일이 붙은 형태를 가지고 있다. 이전 문제에서 n - 2의 타일에 붙이는 타일은 2x1타일이 가로로 2개 붙은 형태만 가능했었는데, 타일이 추가되면서 대신 2x2타일도 가능하게 된 .. [백준] 11726번: 2×n 타일링 - JAVA 🔗 문제 링크 BOJ 11726번: 2×n 타일링 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 📝 풀이 과정 문제를 보고 경우의 수를 하나씩 그려보기로 했다. n = 4까지 그리고 난 뒤 확인해보면 일정한 패턴이 반복됨을 알 수 있었다. 노란색으로 체크된 n - 1의 타일에 세로 타일이 하나 추가된 모습이고, 파란색으로 체크된 n - 2의 타일에 가로 타일이 두 개 추가된 형태를가지고 있다. 따라서, $dp[n] = dp[n-1] + dp[n-2]$라는 점화식을 가지게 된다. 💡 mod 연산을 한 결과값을 출력해야 할 때에는 반.. [백준] 9461번: 파도반 수열 - JAVA 🔗 문제 링크 BOJ 9461번: 파도반 수열 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 📝 풀이 과정 처음 변의 길이가 1인 정삼각형을 기준으로 시계방향으로 정삼각형을 추가하는 수열이다. 한 변의 길이가 2일 때까지는 한 변에 붙는 경우와 두 변에 붙는 경우도 존재하지만, 한 변의 길이가 3 이상이 되면 두 변에 걸쳐 삼각형이 생기는 것을 알 수 있다. N = 6일 때, 1번째와 5번째 삼각형의 두 변의 걸쳐 생성되었고, N = 7일 때, 2번째와 6번째, N = 8일 때, 3번째와 7번째 삼각형의 변을 맞.. [백준] 9095번: 1, 2, 3 더하기 - JAVA 🔗 문제 링크 BOJ 9095번: 1, 2, 3 더하기 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 📝 풀이 과정 문제를 보고 1부터 차례대로 구할 수 있는 모든 경우를 쓰기 시작하였다. (1) 1 --- (2) 1 + 1 2 --- (3) 1 + 1 + 1 2 + 1 1 + 2 3 --- (4) 1 + 1 + 1 + 1 2 + 1 + 1 1 + 2 + 1 1 + 1 + 2 2 + 2 3 + 1 1 + 3 --- (5) 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 1 + 2 + 1 + 1 1 + 1 + 2 + 1 1 + 1 + 1 + 2 2 + 2 + 1 ... 쓰다보면서 일정한 패턴이 반복.. [백준] 2579번: 계단 오르기 - JAVA 문제 링크 BOJ 2579번: 계단 오르기 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 과정 먼저 문제의 핵심은 1번과 2번 규칙이다 계단은 한 번에 한 계단, 두 계단씩만 오를 수 있다 연속된 3개의 계단을 밟으면 안된다 그렇다면, n번째의 계단을 밟는 경우는 몇 가지가 존재할까? n-3을 밟고 n-1번 계단을 밟고 오는 경우와 n-2번을 밟고 오는 경우 2가지가 존재한다. 연속해서 3개의 계단을 밟는 것은 불가능하기 때문에 이외의 경우는 존재하지 않는다. 또한, 조건을 고려하며 한칸을 무조건 뛰는 경우가 발생.. 이전 1 다음
