dp
[백준 파이썬] # 9095 1, 2, 3 더하기
Silver III # 9095 1, 2, 3 더하기 링크 : https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 T = int(input()) for i in range(T): n = int(input()) dp = [0] * (n+3) dp[0] = 1 dp[1] = 2 dp[2] = 4 for i in range(3, n): dp[i] = dp[i-3] + dp[i-2] + dp[i-1] print(dp[-4]) 후기 동적 프로그래밍 문제라는 것을 캐치하면 규칙성을 발견할 수 있다 (동적 프로그래밍 문제인지 여부를 빠르게 파악하는 방법..
[백준 파이썬] # 11727 2xn 타일링 2
Silver III # 11727 2xn 타일링 2 링크 : https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이 n = int(input()) dp = [0] * n dp[0] = 1 for i in range(1, n): if i%2 == 0: dp[i] = dp[i-1] + dp[i-1] - 1 else: dp[i] = dp[i-1] + dp[i-1] + 1 print(dp[-1] % 10007) 후기 이전 문제인 11726과 동일한 유형의 문제다. 수열의 n번째 값을..
[백준 파이썬] # 11726 2xn 타일링
Silver III # 11726 2xn 타일링 링크 : https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 n = int(input()) if n == 1: print(1) else: dp = [0] * n dp[0] = 1 dp[1] = 2 for i in range(2, n): dp[i] = dp[i-1]+dp[i-2] print(dp[-1] % 10007) 후기 결과부터 말하자면 피보나치 수열임을 발견할 수 있다. dp를 이용해서 원하는 값을 찾아가도록 구..
[백준 파이썬] # 1463 1로 만들기
Siver III # 1463 가장 긴 증가하는 부분 수열 링크 : https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 N = int(input()) li = list(range(N+1)) dp = [0 for i in range(N+3)] dp[2] = 1 dp[3] = 1 for i in range(4, N+1): if i%3 == 0 and i%2 == 0: dp[i] = min(dp[i//3], dp[i//2], dp[i-1]) + 1 elif i%3 == 0: dp[i] = min(dp[i//3], dp[i-1]) + 1 elif i%2 == 0:..
[백준 파이썬] # 11053 가장 긴 증가하는 부분 수열 (복습 필요)
Siver II # 11053 가장 긴 증가하는 부분 수열 링크 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 N = int(input()) A = list(map(int, input().split())) dp = [1] * N for i in range(N): for j in range(i): if A[j] < A[i]: dp[i] = max(dp[j]+..
[백준 파이썬] # 1904 01타일
Silver III # 1904 01타일 링크 : https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 풀이 N = int(input()) dp = [0] * (N+1) # indexerror 방지 dp[0] = 1 dp[1] = 2 for i in range(2, N): dp[i] = (dp[i-2] + dp[i-1]) % 15746 # 메모리 크기 제한 print(dp[N-1]) 후기 백준에서 문제 검색 버튼을 이용하면 에러가 발생하는 원인에 대해 쉽..
[백준 파이썬] # 2579 계단 오르기
Silver III # 2579 계단 오르기 링크 : https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 N = int(input()) li = [0]*300 # [0 for i in range(N)] 적용 시 indexerror 발생 dp = [0]*300 for i in range(N): nums = int(input()) li[i] = nums dp[0] = li[0] dp[1] = li[0]+li[1] dp[2] = max(li[1]+li[2], ..
[백준 파이썬] # 1932 정수 삼각형
Silver I # 1932 정수 삼각형 링크 : https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 T = int(input()) li = [] # 입력값 list 만들기 for _ in range(T): nums = list(map(int, input().split())) li.append(nums) # 마지막 인덱스로부터 최대값을 구해나가기 for i in reversed(range(T-1)): for j in range(len(li[i])): li[i][j] = li[i][j] + max(li[i+1][j]..
[백준 파이썬] # 9461 파도반 수열
Silver III # 9146 파도반 수열 링크 : https://www.acmicpc.net/problem/9146 9146번: Linie Na výstupu bude věta "Smernice byla dodrzena.", pokud neexistuje žádná trojice policistů stojících na jedné přímce. Jinak program vypíše na výstup větu "Tito policiste porusuji smernici:" a na každém z dalších řádků bude vždy výpis www.acmicpc.net 풀이 N = int(input()) def P(n): dp = [1, 1, 1] num = int(input()) if num..
[백준 파이썬] # 1003 피보나치 함수
Silver III # 1003 피보나치 함수 링크 : https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 N = int(input()) for _ in range(N): num = int(input()) dp = [[1,0],[0,1]] if num >= 2: for i in range(2, num+1): dp.append([dp[i-1][0]+dp[i-2][0], dp[i-1][1]+dp[i-2][1]]) print(dp[-1][0], dp[-1][1]) else: print(dp[num][0], dp[num][1]) 후기 DP의 첫 ..