«   2022/06   »
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30    
Archives
Today
45
Total
86,235
관리 메뉴

차근차근

[백준 1463] 1로 만들기 본문

대학교/Algorithm

[백준 1463] 1로 만들기

SWKo 2020. 1. 20. 01:55

0. 제목

  • 백준 1463 1로 만들기
  • BOJ 1463 1로 만들기
  • C++ 1로 만들기

1. 문제

https://www.acmicpc.net/problem/1463


2. 풀이

  • DP 방식을 이용하였다.
  • Top-down방식과 Bottom-up방식 중에 Top-down방식을 사용하였다.
  • Top-down방식을 이용할 땐 dp 배열을 10^6 보다 큰 수로 채워놓으면 된다.
  • 먼저 초기값을 설정한 후, dp[i] = 1 + dp[i-1],  dp[i] = min(dp[i], 1 + dp[i/3]), dp[i] = min(dp[i], 1 + dp[i/2]) 와 같은 방법으로 연산횟수의 최솟값을 구한다.

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int dp[1000001];
    int X;
    cin >> X;
    dp[1= 0;
    dp[2= 1;
    dp[3= 1;
    for(int i = 4; i <= X; i++){
        dp[i] = 1 + dp[i-1];    //아래에서 최솟값을 사용하기 위하여 먼저 처리
        if((i % 3== 0)
            dp[i] = min(dp[i], 1 + dp[i/3]);    //min으로 최솟값 찾는 것이 point
        if((i % 2== 0)
            dp[i] = min(dp[i], 1 + dp[i/2]);    //else if 가 아니고 if로 처리
    }
   
    cout << dp[X] << '\n';
    return 0;
}
 

 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 11057] 오르막 수  (0) 2020.01.22
[백준 10844] 쉬운 계단 수  (0) 2020.01.22
[백준 9095] 1,2,3 더하기  (0) 2020.01.20
[백준 11727] 2×n 타일링 2  (0) 2020.01.20
[백준 11726] 2×n 타일링  (0) 2020.01.20
[백준 1463] 1로 만들기  (0) 2020.01.20
0 Comments
댓글쓰기 폼