| 작성자 | 이재영 |
| 일 시 | 2024. 11. 05 (화) 18:00 ~ 21:00 |
| 장 소 | 미래관 429호 자율주행스튜디오 |
| 참가자 명단 | 임혜진, 이재영, 성창민, 김명원, 장원준 |
| 사 진 |  |
목차
1. 백준 1003 피보나치 함수
2. 백준 9095 1,2,3 더하기
이번 모각코도 백준 실버수준에 DP문제를 풀어보려고 한다.
1. 백준 1003 피보나치 함수
문제
fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.
- fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
- fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
- 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
- fibonacci(0)은 0을 출력하고, 0을 리턴한다.
- fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
- 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
- fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.
1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.
출력
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
1) 문제 분석 및 부분 문제 정의
큰 문제는 N번째 피보나치 수열이 0과 1을 호출하는 각각의 연산 횟수이고, 이것을 작은 문제로 나눈다면, 정수 X-1부터 1까지의 연산 횟수를 구하는 것이다.
2) 점화식 도출
간단하게 피보나치 수열을 재귀적으로 구현을 할 때 1과 0의 호출수가 몇번인지 구하는 문제이다. 점화식을 구하기 위해 몇가지 경우를 생각해보자.
n이 2 이상이라고 생각할 때 fibonacci(n) = fibonacci(n-2) + fibonacci(n-1) 이다.
n = 0일 때, [fibo(0)], 0호출 : 1회, 1호출 : 0회
n = 1일 때, [fibo(1)], 0호출 : 0회, 1호출 : 1회
n = 2일 때, [fibo(0), fibo(1)], 0호출 : 1회, 1호출 : 1회
n = 3일 때, [fibo(1), fibo(2)], 0호출 : 1회, 1호출 : 2회
n = 4일 때, [fibo(2), fibo(3)], 0호출 : 2회, 1호출 : 3회
위에 경우를 보았을 때 0과 1이 출력되는 수는 fibo(n-1)의 0과 1 출력 수와 fibo(n-2)의 0과 1 출력 수를 더한 것과 같다. 그럼 결국 점화식은 기존 피보나치 수열과 동일하게 fibonacci(n) = fibonacci(n-2) + fibonacci(n-1)이 된다.
3) 초기 조건 설정
초기 조건은 n이 2 이상일 때 가능하게 하면 되니, dp = [0, 1]로 설정해둔다.
# 메모이제이션
import sys
input = sys.stdin.readline
dp = [[1,0], [0,1]] + [[-1, -1]] * 40
def fibo(n):
if dp[n] != [-1, -1]: return dp[n]
fibo_1 = fibo(n-1)
fibo_2 = fibo(n-2)
dp[n] = [fibo_1[0] + fibo_2[0], fibo_1[1] + fibo_2[1]]
return dp[n]
t = int(input())
for i in range(t):
result = fibo(int(input()))
print(result[0], result[1])# 타뷸레이션
import sys
input = sys.stdin.readline
dp = [[1, 0], [0, 1]] + [[0, 0]] * 41
t = int(input())
for i in range(2, 41):
dp[i] = (dp[i-2][0] + dp[i-1][0], dp[i-2][1] + dp[i-1][1])
for i in range(t):
n = int(input())
print(dp[n][0], dp[n][1])
2. 백준 9095 1,2,3 더하기
문제
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
- 1+1+1+1
- 1+1+2
- 1+2+1
- 2+1+1
- 2+2
- 1+3
- 3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.
출력
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
1) 문제 분석 및 부분 문제 정의
큰 문제는 정수 N이 1, 2, 3의 합으로 나타낼 수 있는 방법의 수이고, 작은 문제는 정수 N에 대하여 N-1, N-2, N-3 각각을 1, 2, 3의 합을 표현하는 방법의 수를 말한다.
2) 점화식 도출
위 문제처럼 몇가지 경우를 나열해보자.
n = 1일 때, 1 => 1가지
n = 2일 때, 1+1, 2 => 2가지
n = 3일 때, 1+1+1, 1+2, 2+1, 3 => 4가지
n = 4일 때, 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1 => 7가지
n = 5일 때, 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+2+2, 2+1+2, 2+2+1, 1+1+3, 1+3+1, 3+1+1, 2+3, 3+2 => 13가지
보면 n이 3보다 클 경우부터 N = N-1 + N-2 + N-3 인 것을 볼 수 있다. 조금 더 이론적으로 가보면 이렇게 할 수 있다.
1,2,3으로 N이라는 수를 만들기 위해서는 (N-1)한 것에 +1, (N-2)한 것에 +2, (N-3)한 것에 +3한 것을 다 더하면 구할 수 있다. 예시를 들어보자.
N = 4일 때
3(N-1)이 1,2,3으로 이루어져 있는 경우의 수에 +1을 하면 4가 되는 경우의 수가 된다. 3은 1+1+1, 1+2, 2+1, 3 이렇게 4가지의 방법이 있고 이 방법에 + 1을 해준다면 1+1+1+1, 1+2+1, 2+1+1, 3+1 총 4가지의 방법을 구할 수 있다.
2(N-2)이 1,2,3으로 이루어져 있는 경우의 수에 +2를 하면 4가 되는 경우의 수가 된다. 2는 1+1, 2 이렇게 2가지의 방법이 있고 이 방법에 + 2를 해준다면 1+1+2, 2+2 총 2가지의 방법을 구할 수 있다.
1(N-3)이 1,2,3으로 이루어져 있는 경우의 수에 +3을 하면 4가 되는 경우의 수가 된다. 1은 1 이렇게 1가지의 방법이 있고, 이 방법에 + 3을 해준다면 1+3 총 1가지의 방법을 구할 수 있다.
이것을 N = 4일 때 경우의 수와 비교해보면 똑같은 것을 볼 수 있다.
3) 초기 조건 설정
n이 4 이상일 때부터 점화식 N = (N-3) + (N-2) + (N-1)이기 때문에 초기 조건은 n이 1, 2, 3일 때 값을 잡아준다면 된다. 그래서 dp = [0, 1, 2, 4] 로 잡아둔다.
# 메모이제이션
import sys
input = sys.stdin.readline
def d(n):
if dp[n] != -1: return dp[n]
dp[n] = d(n-3) + d(n-2) + d(n-1)
return dp[n]
t = int(input())
dp = [0, 1, 2, 4] + [-1] * 10
for _ in range(t):
n = int(input())
print(d(n))# 타뷸레이션
import sys
input = sys.stdin.readline
t = int(input())
dp = [0, 1, 2, 4] + [0] * 10
for i in range(4, 11):
dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
for i in range(t):
print(dp[int(input())])
이렇게 2개의 실버 수준의 문제를 풀어보았다. 이제는 실버 수준의 문제는 어느정도 풀 수 있다고 느끼게 되었다. 다음에는 조금 더 어려운 수준의 문제를 풀어보면 좋을 것 같다.
조금 씩 익숙해지고 있는 것 같아서 좋다. 모각코 주차를 제외하고 몇문제를 더 풀어본 후, 골드 문제를 도전해보려고 한다.