1. 9095번
출처: https://www.acmicpc.net/problem/9095
9095번: 1, 2, 3 더하기
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
www.acmicpc.net
-> 동적 프로그래밍에서는 점화식 구하는게 가장 중요하다는 걸 알게됨
-> 예제 값을 이용해서 관계를 구하고, 점화식 작성하면됨
i=1일 때, 더하기 표한 방법 1 -> hap(1)=1
i=2일 때, 더하기 표한 방법 2(1+1,2) -> hap(2)=2
i=3일 때, 더하기 표한 방법 4(1+1+1,1+2,2+1,3) -> hap(3)=4
hap(4)=7= 1+2+4
-점화식: hap(n) =hap(n-1)+hap(n-2)+hap(n-3)
-방법1 : 재귀함수 이용
-방법 2: 리스트에 append(python에서 재귀함수가 안 될때가 있으니 이 방법을 잘 봐두자)
2. 10870번 : 피보나치 함수 구현.
문제: https://www.acmicpc.net/problem/10870
10870번: 피보나치 수 5
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가
www.acmicpc.net
-정답:
3. 11726번
문제: https://www.acmicpc.net/problem/11726
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
-점화식을 구하는데는 성공해서 재귀함수로 구현하려 했으나 에러 발생 -> 재귀함수 이용하지 않고 구현하는 방법 익히기
-점화식: s(i) = s(i-1) +s(i-2)
-풀이1: 재귀함수 이용
-풀이2 : 리스트 이용해서 풀어보자!!
4. 1149번
문제: https://www.acmicpc.net/problem/1149
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
- 원리는 생각 했는데 코드로 옮기는데 실패 -> 코드로 표현하는 방법 역시 공부하자
-원리: 1. 첫번째 줄에서 최소 값 구하기 2. 이전 줄 선택된 컬럼 빼고 나머지에서 최소값 구하기 (컴퓨터 적으로 생각하는데 부족함이 있는 것 같음)
-풀이 :
- part01
- part02
'백준 > DP' 카테고리의 다른 글
| [코딩테스트]#8. 백준 1010번,11052번,1904번 (0) | 2021.12.17 |
|---|---|
| [코딩테스트] #7. 백준 10844번,2193번,11727번 (0) | 2021.12.14 |
| [코딩테스트]#6. 백준/다이나믹프로그래밍/ 1912번,2156번, 2748번 (0) | 2021.12.13 |
| [코딩테스트]#5. 2579번, 11053번, 1932번 (0) | 2021.12.13 |
| [코딩테스트]#3. 백준 2839번, 1463번, 1003번 (0) | 2021.12.10 |