공부 기록장

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 코드 N = int(input()) dp = [0] * (N+1) for i in range(1, N+1): if i == 1 or i == 2: dp[i] = 1 else: dp[i] = dp[i-1] + dp[i-2] print(dp[N]) N이 1일때부터 쭉 적어가면서 이친수의 개수를 직접 세어보았고, 그 개수들 사이의 규칙을 찾아 점화식을 세웠다. 무작정 규칙을 찾으려고 하기보다..

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 코드 T = int(input()) for _ in range(T): N = int(input()) dp = [0] * (N+1) for i in range(1, N+1): if i == 1 or i == 2 or i == 3: dp[i] = 1 elif i == 4 or i == 5: dp[i] = 2 elif i == 6: dp[i] = 3 elif i == 7: dp[i] = 4 elif i ==..

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]..