로그 남기기

9625 - BABBA 문제 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했다. 한 번 더 누르니 BA로 바뀌고, 그 다음에는 BAB, 그리고 BABBA로 바뀌었다. 상근이는 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게되었다. 버튼을 K번 눌렀을 때, 화면에 A와 B의 개수는 몇 개가 될까? 코드 K = int(input()) dp = [(0, 0)] * (K+1) if K == 1: print(0, 1) elif K == 2: print(1, 1) else: dp[1], dp[2] = (0, 1), (1, 1) for i in range(3..

1788 - 피보나치 수의 확장 문제 수학에서, 피보나치 수는 위의 점화식과 같이 귀납적으로 정의되는 수열이다. 위의 식에서도 알 수 있듯이, 피보나치 수 F(n)은 0 이상의 n에 대해서만 정의된다. 하지만 피보나치 수 F(n)을 n이 음수인 경우로도 확장시킬 수 있다. 위의 식에서 n>1인 경우에만 성립하는 F(n)=F(n-1)+F(n-2)를 n 0: print(1) else: print(0) print(arr[abs(N)]) 한마디 음수의 피보나치를 어떻게 처리해야할까 걱정했는데 노트에 적어보니 양수의 피보나치와 값은 똑같았다. n이 짝수인지 홀수인지에 따라 부호만 달라지는 것을 알 수 있었다. 1788번: 피보나치 수의 확장 첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다..

1912 - 연속합 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 코드 import sys input = sys.stdin.readline N = int(input()) arr = list(map(int, input().split())) dp = [0] * (N+1) dp[1] = arr[0] for i in range(2, N+1): dp[i] = max(dp[i-1] + arr[i-1], arr[i-1])..

9507 - Generations of Tribbles 문제 꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다. 그래서 다음과 같은 피보나치를 만들었다. 꿍만의 피보나치 함수가 koong(n)이라고 할 때, n 3 : koong(n − 1) + koong(n − 2) + koong(n − 3) + koong(n − 4) 이다. 여러분도 꿍 피보나치를 구해보아라. 코드 T = int(input()) arr = [int(input()) for _ in range(T)] max_num = max(arr) dp = [0] * (max_num + 1)..

1463 - 1로 만들기 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 코드 N = int(input()) dp = [0] * (N+1) for i in range(2, N+1): dp[i] = dp[i-1] + 1 if i % 3 == 0: dp[i] = min(dp[i], dp[i//3] + 1) if i % 2 == 0: dp[i] = min(dp[i], dp[i//2] + 1) print(dp[N]) 한마디 memoization 방식을 이용해 d..

11726 - 2 X n 타일링 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 코드 N = int(input()) dp = [0] * (N+1) if N == 1: print(1) elif N == 2: print(2) else: dp[1], dp[2] = 1, 2 for i in range(3, N+1): dp[i] = dp[i-1] + dp[i-2] print(dp[N] % 10007) 한마디 손으로 조금만 그려보면 점화식을 쉽게 찾을 수 있다. 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www..