1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
규칙을 찾아봅시다
X=2일 때, 1 (2/2=1)
X=3일 때, 1 (3/3=1)
X=4일 때, 2 (4/2=2 2/2=1)
X=5일 때, 3 (5-1=4, 4/2=2 2/2=1)
X=6일 때, 2 (6/3=2, 2/2=1)
X=7일 때, 3 (7-1=6, 6/3=2, 2/2=1)
1. 3의 배수일 때 => 3으로 나눔
2. 3의 배수가 아니고 2의 배수일 때 => 2로 나눔
3. 2의 배수, 3의 배수도 아닐 때 => 1을 뺌
T(4) = 1+ T(2)
T(5) = 1+T(4)
T(6) = 1+T(2)
T(7) = 1+T(6)
T(8) = 1+T(4)
T(9) = 1+ T(3)
근데 이렇게 했을 경우
T(10) = 1+ T(5) = 1+ 1+ T(4) = 1+1+1+T(2) = 4가 되는 데,
사실은 T(10) = 1+T(9) = 1+1+T(3) = 3으로 최솟값이 만들어진다
,,
[백준 1463번 1로 만들기/ C++](DP) (tistory.com)
[백준 1463번 1로 만들기/ C++](DP)
www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 민망하지만..난 사실..dp에 굉.장.히. 약하다... 어떤 문제가 dp인지도 잘
ssinee.tistory.com
[백준] 1463 1로 만들기 C++(DP) (velog.io)
[백준] 1463 1로 만들기 C++(DP)
백준 1463
velog.io
'‡ CODING TEST STUDY ‡ > º 백준' 카테고리의 다른 글
| [백준 1912번 C++] 연속합 (0) | 2023.10.08 |
|---|---|
| [백준 2193번 C++] 이친수 (0) | 2023.10.07 |
| [백준 9095번 C++] 1,2,3 더하기 (0) | 2023.10.07 |
| [백준 11727번 C++] 2xn 타일링 2 (0) | 2023.10.07 |
| [백준 11726번 C++] 2xn 타일링 (0) | 2023.10.07 |