[C#]백준 1463 1로 만들기 - Hide

반응형

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

문제 요약

세 종류의 연산을 이용해서 주어진 수를 1로 만들 때 필요한 연산의 최소 횟수 출력하기

 

 

 

참고

주어진 연산들을 이용해 i를 1로 만드는 연산의 최소 횟수는

(i-1의 최소 횟수+1, %2나%3을 사용해 1로 만드는 연산의 최소 횟수) 두 가지 경우가 있고,

두 경우 중 더 작은 수를 고르면 된다.

i	i-1을 먼저 했을 경우	횟수	%2이나 %3을 먼저 했을 경우	횟수	최소 횟수
0					0
1					0
2	1	1	1	1	1
3	2->1	2	1	1	Math.Min(2, 1) => 1
4	3->1	2	2->1	2	2
5	4->3->1, 4->2->1	3			3
6	5->4->3->1, 5->4->2->1	4	3->1, 2->1	2	Math.Min(4, 2) => 2
7	6->3->1, 6->2->1	3			3
8	7->6->3->1, 7->6->2->1	4	4->3->1, 4->2->1	3	Math.Min(4, 3)=> 3
9	8->4->3->1, 8->4->2->1	4	3->1	2	Math.Min(4, 2) => 2
10	9->3->1	3	5->4->3->1, 5->4->2->1	4	Math.Min(3, 4) => 3

 

 

 

풀이

int n=int.Parse(Console.ReadLine());
var a=new int[n+1];
for(int i=1;i++<n;)
{
    a[i]=a[i-1]+1;
    if(i%2==0)a[i]=Math.Min(a[i],a[i/2]+1);
    if(i%3==0)a[i]=Math.Min(a[i],a[i/3]+1);
}
Console.Write(a[n]);

예제 2의 경우 0부터 10까지 각각의 i를 1로 만드는 연산의 최소 횟수를 담은 배열 = {0,0,1,1,2,3,2,3,3,2,3}이 된다.

 

 

 

숏코딩

int n=int.Parse(Console.ReadLine()),i=1;var a=new int[n+1];
for(;i++<n;)a[i]=Math.Min(a[i-1],Math.Min(i%2==0?a[i/2]:int.MaxValue,i%3==0?a[i/3]:int.MaxValue))+1;Console.Write(a[n]);

---

이게 DP???? 너무 똑똑한걸..?