정리용

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 1. 코드설명 f = int(input()) dp= [1, 2, 4] for i in range(3, 10) : dp.append(dp[i-1] + dp[i-2] + dp[i-3]) for i in range(f) : n = int(input()) print(dp[n-1]) 2. 주의사항 dp의 기본적인 유형

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 1. 코드 설명 for _ in range(int(input())) : n = int(input()) arr = [1]*(n+4) arr[0] = 1 arr[1] = 1 arr[2] = 2 for i in range(n) : arr[i+3] = arr[i] + arr[i+1] print(arr[n-2]) 2. 주의사항 없다 시간 제한도 넉넉해서 for문 마다 리스트를 새로 만들수도 있으며 수열도 문제에..

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 1. 코드 설명 n = int(input()) dp = [0]*(n+1) dp[0] = 1 dp[1] = 3 for i in range(n-2): dp[i+2] = dp[i]*2 + dp[i+1] print(dp[n-1] % 10_007) 2. 주의 사항 11726 타일링 1과 똑같은 문제이다 n = 5나 6정도 까지 직접 구해가며 규칙을 찾으면 코드 자체는 아주 쉽다

1. 코드 (실패) n= int(input()) dp = [[0]*9 for j in range(n+1)] dp[0] = [1]*9 for i in range(1,n) : for j in range(9): if j == 0 : dp[i][j] = dp[i-1][j-1] + i elif j == 8 : dp[i][j] = dp[i-1][j-1] else : dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] print(dp) print(dp[n-1]) print(sum(dp[n-1])%1000000000) 2. 주의사항 첫번째 자리를 기준으로 1~9으로 분류하여 규칙을 찾으려했으나 끝 자리 기준으로 0 의 규칙도 고려하여 규칙을 찾아야헀다 n = 5 까진 j==0 일떄 dp[i-1][j-..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 1. 코드 #import sys #input = sys.stdin.readline n=int(input()) dp = [0]*(n+2) lst=[0]*(n+2) for i in range(1,n+1): lst[i]=int(input()) dp[1] = lst[1] dp[2] = lst[1] + lst[2] #print(dp) for i in range( 3, n+1) : dp[i] = max(dp[..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 1. 코드 설명 1) 전형적인 dp 풀이 ( 0 행렬을 만들고 채워가는 방식 ) n = int(input()) lst = list(map(int, input().split())) dp = [0] * n dp[0] = lst[0] print(dp) for i in range(1, len(lst)): dp[i] = max(lst[i], dp[i-1] + lst[i]) print(dp) print(max(dp))..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 1. 코드 설명 n = int(input()) tri =[list(map(int, input().split())) for _ in range(n)] #tri = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] #n=5 for i in range(1,n): for j in range(i+1): if j == 0: tri[i][j] = tri[i][j] + tri[i-1][j] #print('j == 0 ',tri) el..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 1. 코드 설명 n=int(input()) stairs=[0]*(n+3) for i in range(n): stairs[i]=int(input()) dp = [0]*(n+3) dp[0]=stairs[0] dp[1]=stairs[0]+stairs[1] dp[2]=max(stairs[2]+stairs[0], stairs[2]+stairs[1]) for i in range( 3, n) : dp[i] = max(st..