DHistory

문제 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 """ 1. 계단을 한 계단 씩 또는 두 계단씩 오를 수 있다. 2. 연속된 세 개의 계단을 모두 밟아서는 안된다. 3. 마지막 도착 계단은 반드시 밟아야한다. d[n]: n번째 계단을 밟았을 때 최대 점수 OX | O OXO | O 1. 직전 계단을 밟지 않은 경우 d[i - 2] + a[i]이다. 2. 직전 계단을 밟은 경우 d[i - 1]이 아닌 d[i - 3]인 이유는 d[i - 1]에서 직전 계단을 밟았을 때, 최대 점수일 수 있기 때문이다. d[i - ..

문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 """ d[n] = 가로의 길이가 n일 때 타일을 채울 수 있는 방법의 수 타일의 크기는 1x2 / 2x1이 있다. d[1] = 1 d[2] = 2 # 2 x 1로 만들 수 있는 방법의 수 + 1 x 2로 만들 수 있는 방법의 수 d[i] = d[i - 1] + d[i - 2] """ n = int(input()) def solution(n): d = [0] * (n + 1) d[0] = 1 d[1] = 1 for i in range(2, n + 1): d[i] = (d[i..

문제 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 """ 0 1 1 2 3 5 8 f(0) = f(0) f(1) = f(1) = 1f(1) + 0f(0) f(2) = f(1) + f(0) = 1f(1) + 1f(0) f(3) = f(2) + f(1) = 2(f1) + 1f(0) f(4) = f(3) + f(2) = 3f(1) + 2f(0) f(5) = f(4) + f(3) = 5f(1) + 3f(0) f(6) = f(5) + f(4) = 8f(1) + 5f(0) => 0과 1의 개수가 피보나치 수열을 이룬다. """ import sys t = int(sys.stdin.readline().rstri..

문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 """ 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. 연산을 사용하는 횟수의 최솟값을 출력 d[n]: n을 만들기 위한 연산의 최솟값 """ n = int(input()) def solution(n): d = [10 ** 6 + 1] * (n + 1) d[0] = d[1] = 0 for i in range(1, n + 1): if not i % 2: d[i] = min(d[i], d[i // 2] + 1) if not i % 3: d[i] = min(d[i], d[i // 3] + 1) d[i]..

문제 15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 """ 0번째 0 1번째 1 2번째부터는 바로 앞 두 피보나치 수의 합 """ import sys n = int(sys.stdin.readline().rstrip()) def solution(n): a, b = 0, 1 for i in range(2, n + 1): if not i % 2: # 미리 나누어서 저장해야한다. # 큰 숫자가 되면 비트를 많이 사용하기 때문에 연산 속도가 오래걸린다. a = (a + b) % 1000000007 else: b = (a + b) % 1000000007 return a if not n % 2 else b prin..

문제 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 풀이 """ d[n]: n일 때, 가장 긴 구간이 되는 길이 """ import sys n = int(sys.stdin.readline().rstrip()) numbers = list(map(int, sys.stdin.readline().rstrip().split()))[:n] def solution(numbers): # 가장 긴 구간이 되는 길이의 최솟값은 1이다. d1 = [1] * len(numbers) d2 = [1] * len(numbers) for ..

문제 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 """ d[n]: n kg을 가져갈 설탕 봉지의 최소 개수 """ n = int(input()) INF = 10**9 + 1 def solution(n): d = [INF] * (n + 1) for i in range(3, n + 1): if not i % 3: d[i] = min(d[i], i // 3) if not i % 5: d[i] = min(d[i], i // 5) d[i] = min(d[i], d[i - 3] + 1, d[i - 5] + 1) retu..

문제 25644번: 최대 상승 미래를 예측하는 능력이 있는 정균이는 앞으로 $N$일간 ANA 회사의 주가가 어떻게 변하는지 정확히 예측할 수 있다. 정균이는 예측한 결과를 바탕으로 ANA 회사의 주식 한 주를 적당한 시점에 사고 www.acmicpc.net 풀이 import sys n = int(sys.stdin.readline().rstrip()) INF = 10**9 + 1 stocks = [INF] + list(map(int, sys.stdin.readline().rstrip().split())) def solution(a): d = [0] * len(a) min_value = INF for i in range(1, len(a)): if min_value > a[i - 1]: min_value = ..

문제 19947번: 투자의 귀재 배주형 2020년에 학교로 복학한 주형이는 월세를 마련하기 위해서 군 적금을 깨고 복리 투자를 하려고 한다. 주형이가 하려는 투자에는 3가지 방법의 투자 방식이 있다. 1년마다 5%의 이율을 얻는 투자 ( www.acmicpc.net 풀이 """ A: 1년마다 5%의 이율을 얻는 투자 B: 3년마다 20%의 이율을 얻는 투자 C: 5년마다 35%의 이율을 얻는 투자 투자 방식은 매년 변강할 수 있다. 매년 이율은 소쉄 이하를 버림해서 받는다. 11,111 A: 1년후 555 B: 3년후 2,222 C: 5년후 3,888 C 방식으로 투자 시 4년이 지난 시점이라면 받을 수 있는 이자는 0원 d[n] = n년 후 받을 총액 """ h, y = map(int, input()...

문제 13301번: 타일 장식물 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개 www.acmicpc.net 풀이 """ 피보나치수열 d[n] = d[n - 1] + d[n - 2] 정사각형 2개가 합쳐 다음 정사각형과 동일하다. 80번째 사각형은 81번째 정사각형과 80번째 정사각형으로 이루어져있다. """ n = int(input()) def solution(n): d = [0] * (80 + 2) d[1] = 1 for i in range(2, n + 2): d[i] = d[i - 1] + d[i - 2] return 2 * d[n + 1] + 2 * d[n] ..