![]()
https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 아이디어 DP 문제이다. 아래와 같이 각 한 인덱스를 기준으로 최솟값을 구해나가면 쉽게 구할 수 있다. 즉, 아래와 같은 점화식을 추론할 수 있다. dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + datas[i][0] dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + datas[i][1] dp[i][2] = min(dp[i-1]..
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 아이디어 DP문제이다. 우선 n이 1~5일 때를 구해서 규칙을 찾았다. n 경우의 수 1 1 2 2 3 3 4 5 5 8 . . . n의 경우의 수는 n-1의 경우의 수 + n-2의 경우의 수 였다. 이렇게 규칙을 찾고 찾은 식을 바탕으로 코드를 작성해보았다. 전체 코드 import sys input = sys.stdin.readline n = int(input()) if n == 1: print(1) else: dp..
https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 아이디어 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다. 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다. 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다..
https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 아이디어 경우의 수를 구하는 문제라서 dp로 풀기로 했다. 먼저 식을 도출하기 위해 1~5까지 구하고, 의심되는 식을 사용해서 7과 10의 경우의 수를 구해보았다. 1 1 1 2 1+1 2 2 3 1+1 2+1 1+2 3 4 4 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 7 5 1+1+1+1+1 1+1+1+2 -> 이 조합으로 4가지 1+1+3 -> 이 조합으로 3가지 1+2+2 -> 이 조합으로 3가지 2+3 -> 이 조합으로 2가지 13 . . . 위와 같이 n번째의..
