https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net ''' 2*n 크기의 직사각형을 1*2, 2*1 타일로 채우는 방법의 수 1과 2를 더해서 총 n을 만드는 경우의 수를 구하면 됨 ''' n = int(input()) dp = [0]*(max(3,n+1)) dp[1], dp[2] = 1, 2 if n >= 3: for i in range(3,n+1): dp[i] = dp[i-2] + dp[i-1] print(dp[n] % 10007) 1,2,3 더하기랑 거의 동일한 ..

https://www.acmicpc.net/problem/1149 1149번: RGB거리첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나www.acmicpc.net'''인접한 집들의 색이 같지 않아야 함R,G,B 세 가지 색으로 칠함i번째 집을 칠하는 비용은 i-1번째 집에 따라 달라짐dp[i][color]를 i번째 집까지 칠하는 데 드는 최소 비용으로 설정'''import sysinput = sys.stdin.readlineN = int(input())cost = [list(map(int, input().split())) for _ in ..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net ''' 한번에 계단 +1 or +2 연속된 세 계단 밟으면 안됨(+1+1+1 +2+2+2 x) 마지막 도착 계단은 반드시 밟아야 됨 -> 그럼 마지막 칸에서 처음으로 가는 걸 생각해보면? 점수의 최댓값 사고 방식(탑다운): 어디에서 올라왔을까? 한칸 전? 두칸 전? ''' import sys input = sys.stdin.readline n=int(input()) s=[int(input()) for _ in..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net import sys input = sys.stdin.readline T = int(input()) for _ in range(T): n = int(input()) dp = [0]*(max(4,n+1)) dp[1], dp[2], dp[3] = 1, 2, 4 if n >= 4: for i in range(4, n+1): dp[i] = dp[i-1] + dp[i-2] + dp[i-3] print(dp[n]) 처음에 dp = [0] * (n+1) 했다가 런타임 에러가 떴었다. 이유: n=3 이하인 경우..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net ''' 길이가 N인 계단 수 몇개? 1

https://www.acmicpc.net/problem/4883 4883번: 삼각 그래프 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 www.acmicpc.net import sys input = sys.stdin.readline K = 1 while True: N = int(input()) if N == 0: break dp = [] for i in range(N): dp.append(list(map(int, input().split()))) ans = 0 dp[1][0] += dp[0][1] dp[1][1] += min(dp[0][1],..