티스토리 뷰

728x90

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

 

1463번: 1로 만들기

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

www.acmicpc.net

동적계획법 C++

문제는 위에 사진 참고 (설명 매우 귀찮다 딱히 요약할 것도 없응께)

N의 범위는 1부터 10^6 까지

 

접근방법

n개의 정수 배열을 사용한다. 배열에는 해당 수가 1이 되는데에 필요한 연산의 최소 횟수가 저장된다.

1: 0회, 2: 1회, 3: 1회까지 미리 저장해두고

4부터는 [ 1을 뺀 수의 연산 최소횟수 + 1 , 3으로 나눈 값의 연산 최소횟수 + 1 (3으로 나누어질때만), 2로 나눈 값의 연산 최소횟수 + 1 (2로 나누어질때만) ] 이 중 가장 작은 값을 해당 인덱스의 배열에 저장한다. 

(설명 진짜 못해먹겠음)

 

이제 DP에 적응한 것 같다. 빨리 푼다.

처음에 한 번 틀렸는데 1에 1저장해서.. 1이 1이되려면 연산횟수는 0..나처럼 멍청한짓 하는 사람 없겠지

 

소스코드

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    int results[n+1];
    results[1] = 0;
    results[2] = 1;
    results[3] = 1;
    for(int i = 4; i <= n; i++){
        results[i] = results[i-1]+1;
        if(i % 3 == 0){
            results[i] = min(results[i], results[i/3]+1);
        }
        if(i % 2 == 0){
            results[i] = min(results[i], results[i/2]+1);
        }
    }
    cout << results[n];
    return 0;
}
728x90
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
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
31
글 보관함