복습2

2020-02-14

복습 2 (2/14)

1로 만들기

            //1
            if(a%3 == 0 && dp[a/3] == 0){
                qu.add(a/3);
                dp[a/3] = dp[a] + 1;
            }
            //2 
            if(a%2 == 0 && dp[a/2] == 0){
                qu.add(a/2);
                dp[a/2] = dp[a] + 1;
            }
            
            //3
            if(dp[a-1] == 0) {
	            qu.add(a-1);
	            dp[a-1] = dp[a] + 1;
            }
            

며칠 전에 풀었던 문제였음에도 불구하고 30min가 걸렸다..! 으아

  • 포인트는dp에 들어있는 값은 계속 사용할 것이고
  • 최소값이 들어있게 하려면
  • 처음 방문했던 값만 존재해야 한다
  • 그 얘기는 dp[0] -> dp[i]로 변할 때 단 한번만 가게 해야 최소값을 저장해 놓을 수 있다.