- 문제 : https://www.acmicpc.net/problem/1463
1. 생각해보기
A. 해당 문제가 DP 문제인 이유
1) 연산을 사용하는 횟수의 최솟값 => 최적의 해를 찾아야 함
2) 이전 연산에서 3가지가 계속 반복되어야 함 => 단순히 분할정복 알고리즘으로는 안됨
B. 알고리즘
- 정수는 N을 입력받고, 1차원 DP 배열을 하나 생성한다.
- 1차원 DP에 N까지의 최소 경우의 수를 담는다. (3까지는 초기 세팅 필요)
- for문을 돌리면서 DP[N]을 채워 나감.
- DP[N]은 = 3번, 2번, 1번 중에서 제일 경우의 수가 작은 값으로 세팅한다
- 출력은 DP[N]
C. 시간복잡도
N의 최솟값을 구하는데 for문을 N-3돌리게 됨으로, O(N)의 시간복잡도를 가진다.
=> 다음과 같이 조건에 시간 제한은 0.15초이다 1억(10^8)연산당 1초라고 가정했을때
0.15초는 10^8 * 0.15 = 15,000,000이다.
=> 0.15초 동안 15 * 10^6연산이 가능함으로, 최대치 10^6을 대입하면 0.15초안에 풀 수 있다.
2. 결과
https://github.com/moonlight-duck/study-algorithms/pull/24
feat: 백준 1463번 DP 문제 풀기 2 by min-99 · Pull Request #24 · moonlight-duck/study-algorithms
📌 문제 정보 문제 링크 : https://www.acmicpc.net/problem/1463 카테고리 (예: 구현, 탐색, DP) : DP ✏️ 풀이 방법 결과 (성공/실패) : 성공 풀이 시간 : 1h 풀이 방법 : https://min-99.tistory.com/34 참고한 글 링크 :
github.com
'알고리즘' 카테고리의 다른 글
| Adding 1s, 2s, and 3s (DP, + 해석) (0) | 2025.11.17 |
|---|---|
| Greedy(탐욕 알고리즘) (0) | 2025.11.15 |
| DP 문제 시도하기(+ 백준 2579 계단오르기) (0) | 2025.11.11 |
| DP 개념 (0) | 2025.11.11 |
| BFS(백준 : 토마토-7576문제) 접근 방법 (0) | 2025.10.30 |