DP_1로 만들기_백준_1463

-문제-

 

-문제접근-

 

위 문제는 주어진 자연수 n을 1로 만들기 위해 필요한 최소 연산 횟수를 DP를 이용해 구하는 문제입니다.

 

아래의 조건이 중요하며 확실하게 인지를 해야 합니다.

 

• n에서 1을 빼는 연산
• n이 2로 나누어 떨어지면 2로 나누는 연산
• n이 3으로 나누어 떨어지면 3으로 나누는 연산

 

d[1] =0 : 1은 이미 목표 값이기에 1을 1로 만드는데 필요한 연산 횟수는 0입니다.

 

1은 0번의 횟수를 갖기에 for문은 i를 2부터 n보다 작거나 같을 때로 잡아서 위의 조건을 적용시켜줍니다.

 

1번 조건

d[i] = d[i - 1] + 1; : 가장 기본적인 연산인 1을 빼는 것이며 i를 1로 만들기 위한 연산 횟수는 i-1을 1로 만드는 최소 횟수에 1을 더한 값입니다.

 

2번 조건

if (i % 2 == 0) d[i] = min(d[i], d[i / 2] + 1);

: i/2를 1로 만드는 최소 연산 횟수에 1(나누는 연산)을 더한 값과 기존의 d[i] 값 중 최솟값으로 갱신하여 줍니다.

 

3번 조건

if (i % 3 == 0) d[i] = min(d[i], d[i / 3] + 1);

: i/3을 1로 만드는 최소 연산 횟수에 1을 더한 값과 비교하여 최솟값으로 갱신합니다.

 

위 과정들을 통해 모든 i에 대해 1로 만드는 최소 연산 횟수가  d[i]에 갱신 되면서 저장됩니다.

 

-전체 코드-

 

 

-END-