ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 백준 1463 : 1로 만들기
    알고리즘 문제/DP 2017. 10. 9. 22:07
    반응형


    백준 1463 1로만들기

    해설

    dp로 불어보았다. 

    문제를 딱 봤을 때 우선 음.. 확실히 3으로 나누는 것이 이동수를 크게 줄이는 이득부분이니까 나누는게 좋다. 라고 생각했고, n에서 1까지 내려가는 것을 연산하였다.

    그런데 반례는 예제에서도 있듯이 10은, 10 ->9->3->1 이 최소이동이며  내가 생각한대로 하면

    10->5->4->2->1 이므로 이동횟수가 하나 더 많았다.


    dp의 배열을 이용하면서 1에서부터 차근차근 해당수로 올라가면서 1에서부터의 최소거리를 구한다면 우리가 원하는 방식으로 알고리즘은 동작한다. 어떤 수 n는 default로 하나 작은 수[n-1] 에서 1을 더한만큼의 거리를 가진다. 그리고 그게 2로 나누어지고 d[n-1]+1보다 d[n/2]+1이 작다면 대체, 그게 3으로 도 나누어지고 d[n-1]+1, d[n/2]+1 보다 작다면 d[n/3]+1 로 대체한다. 

    6인경우를 생각해보자. 6은 확실히 d[5]+1, d[3]+1, d[2]+1 이다. 이 셋중에서 무엇이 제일 작은 값인지는 d 배열의 값을 알아야 가능하다. 그래서 코딩에서는 비교하는 조건문이 들어가는 이유다. 반드시 배수가 +1보다 효율적인 반례는 위에서 살펴보았던 자연수 10이다.

    10은 확실히 d[9]+1, d[5]+1 이다. 이 둘중에서 작은 값은 d[9]+1 이기 때문이다.

    n의 경우는 어떨까? 잘 작동한다. 이는 모든 자연수 입력값에서도 잘 동작한다. 

    왜그럴까? 우리는 차근차근 모든 경우의 수 (+1, *2, *3) 를 비교하며 숫자들의 최소 거리를 저장하며 진행했기때문에 앞으로 진행 될 수도 항상 최소 거리이다. 이 문제가 나한테 dp 입문이였다.


    소스보기

     https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/p1463.c





    반응형

    '알고리즘 문제 > DP' 카테고리의 다른 글

    백준1126 같은탑  (0) 2017.12.05
    BOJ 1520 : 내리막길  (0) 2017.11.11
    백준 9095 : 1, 2, 3 더하기  (0) 2017.10.10
    백준 11727: 2*n 타일링2  (0) 2017.10.09
    백준 11726 : 2*n 타일링  (1) 2017.10.09
    백준 1463 : 1로 만들기  (2) 2017.10.09

    댓글 2

    • ㅇㅇ 2019.01.07 10:49

      왜 배열 d는 전역변수로 선언하는건가요? main 내부에 선언하니 쓰레기값이 출력되네요..

      • gaelim 2019.01.24 13:48 신고

        지역변수와 전역변수와 할당되는 메모리 영역이 다릅니다. C, C++ 에서는 전역변수인 경우 0으로 초기화가 됩니다.

        아래 링크를 참조해보세요.

        http://soen.kr/lecture/ccpp/cpp1/7-1-1.htm




Designed by Tistory.