공부 기록장

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 코드 n = int(input()) dp = [0] * (n+2) # (n+1) 하면 왜 런타임 에러가 나는지 ?? dp[1] = 1 dp[2] = 2 for i in range(3, n+1): dp[i] = dp[i - 2] + dp[i - 1] print(dp[n] % 10007) 이와 비슷한 타일링 문제를 이코테 책으로 DP 공부하면서 풀어봤던 기억 때문에 점화식을 구하는 것은 그렇게 어렵지 않았다. 한 가지 의..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 코드 T = int(input()) dp = [[0, 0] for _ in range(41)] for i in range(0, 41): if i == 0: dp[i][0], dp[i][1] = 1, 0 elif i == 1: dp[i][0], dp[i][1] = 0, 1 else: dp[i][0], dp[i][1] = dp[i-1][0] + dp[i-2][0], dp[i-1][1] + dp[i-2][1] for _ in range(T): n = int(input()) print(dp[n][0]..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 코드 T = int(input()) dp = [0 for _ in range(11)] dp[1] = 1 dp[2] = 2 dp[3] = 4 for i in range(4, 11): dp[i] = dp[i-1] + dp[i-2] + dp[i-3] for _ in range(T): n = int(input()) print(dp[n]) 방법의 수를 n이 1일 때부터 차례대로 적어가면서 숫자들 사이의 규칙을 찾아 점화식을 구하려고 시도를 했다. N이 5인 경우에 대해서 경우의 수를 잘못 세고 내가 짐작..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 코드 n = int(input()) d = [0] * (n + 1) # d[i]에 저장되는 값은 i를 1로 만드는 최소 연산 횟수 # 상향식 풀이 : 제일 작은 인덱스의 수부터 목표하는 값으로 향하는 것 for i in range(2, n + 1): # if 문을 하지 않아도 밑의 조건문에서 최소값으로 교체되기 때문에 어짜피 셋 다 시도하는 것과 같으 결과 d[i] = d[i - 1] + 1 if i % 3 == 0: d[i] = min(d[i], d[i // 3] + 1) if i % 2 == 0: d[i] ..