기록방

👉 문제링크 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 🔸 문제 분석 🔸 1x2, 2x1, 2x2 타일을 채우는 경우의 수를 출력한다. 점화식은 dp[n] = dp[n-1] + dp[n-2]*2 이다. 🔸 코드 🔸 arr = [1,1] for _ in range(int(input())-1): arr.append((arr[-1]+arr[-2]*2)%10007) print(arr[-1]) 🔸 코드 해석 🔸 리스트의 초기값을 1,1로 두고 점화식을 적용한다. 문제 조건에 따라 10007의 나머지로 계산한다. 🔸 end 🔸 2xn타일 1을 풀..

👉 문제링크 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 🔸 문제 분석 🔸 타일을 채울 수 있는 경우의 수를 출력한다. 점화식은 dp[n] = dp[n-1] + dp[n-2] 이다. 🔸 코드 🔸 n = int(input()) dp = [1,1] for i in range(1,n): dp.append((dp[-1]+dp[-2])%10007) print(dp[n]) 🔸 코드 해석 🔸 dp 리스트의 인덱스 0, 1은 1로 초기화 한다. 점화식에 따라 입력 값(n) 만큼 반복하며 dp리스트를 채운다. 값을 채울 때 문제 조건에 따라 1..

👉 문제링크 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 🔸 문제 분석 🔸 숫자 리스트를 입력받고, 특정 구간에 대한 합을 출력한다. 🔸 코드 🔸 import sys n, m = map(int, sys.stdin.readline().rstrip().split()) arr = list(map(int, sys.stdin.readline().rstrip().split())) acc = [0] for i in arr: acc.append(acc[-1] + i) for _ in range(m)..

👉 문제링크 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 🔸 문제 분석 🔸 규칙처럼 회오리 모양으로 삼각형이 늘어갈때 가장 큰 변의 길이를 출력하는 문제이다. dp[0] ~ dp[9] 까지의 10개 값은 문제에서 주어졌다. 인덱스 3(입력 값 4)부터 점화식이 적용된다. P(N) = P(N-2) + P(N-3) 🔸 코드 🔸 dp = [1,1,1,2,2,3,4,5,7,9] for _ in range(int(input())): n = int(input()) if n

ㅊ👉 문제링크 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 🔸 문제 분석 🔸 입력받은 수를 1,2,3으로 만들 수 있는 경우의 수를 출력한다. dp와 회귀 방법 두 가지로 풀이 가능한데, dp로 풀이했다. 1,2,3 을 만드는 경우의 수는 다음과 같다. (1) : 1 >> 1개 (2) : 1+1 , 2 >> 2개 (3) : 1+1+1, 1+2, 2+1, 3 >> 4개 1,2,3은 기본값으로 저장해두고, 4부터 '1,2,3 더하기 어떤 수'의 경우의 수를 생각한다. 1+3 : 1 + (3을 표현 할 수 있는 경우의 수) >> 1+(1+1+1), 1+(1+2), 1+(2+1), 1+(3) 2+2 : 2 + ..