백준 1463 1로 만들기

문제 URL : https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

문제접근법 : 문제는 dp입니다. 그러나 알고리즘에는 하나의 정답만 있는것이 아닌

여러가지 사용할수있기에 저는 두가지 방법으로 이문제를 해결했습니다

dp 방법과 bfs방법 두가지방법 

 

첫번째는 dp방법을 사용하기위해선 n에서 1을 만든다고했으니 n에서 - > 1을 만드는 경우를 생각하면 답이

힘들게 나오기에 1 -> n을 만드는 방법으로 역으로 생각하면 문제는 쉽게풀립니다.

for문을 2부터시작하여 n까지 달린후 i가 2의 약수인경우 dp[i/2]번째에서 구했던 수에서 더하기 1을해주면되고

i가 3의 약수라면 dp[i/3]번째에서 구했던 count를 +1을 해주면되는것이고

1을 빼는경우는 dp[i-1]에서 +1을 해주면 됩니다. 

문제는 연산을 최소화 하기위해 dp[i/2]와 dp[i/3], dp[i-1] 의 최솟값중 +1을하면 n번째까지 얼마든지 구할수있는문제입니다.

 

소스코드 : 

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 32 33

#include <iostream> #include<cstdio> #include <algorithm> #include <vector> #include <cmath> #include <queue> using namespace std; #define type_in in int a[1000001]; #define M 9999999 int min3(int a,int b,int c) {     int mi=min(a,b);     return mi<c?mi:c; } int main(void) {     int n;     scanf("%d",&n);     for(int i=2;i<=n;i++)     {         int x,y,z;         x=y=z=M;         if(i%2==0)             x=a[i/2];         if(i%3==0)             y=a[i/3];         z=a[i-1];         a[i]=min3(x,y,z)+1;     }     printf("%d\n",a[n]); }

cs

 

2번째 방법입니다.

그것은 bfs를 이용하는 방법입니다. n부터 시작해서 1을 만들기위해 최소연산을 하기위한것이므로

문제그대로 3으로 나누어떨어지면 3으로 나누고 2로나누어 떨어지면 2로 나누는 방법을

또 1을 빼는 형식으로 bfs를 사용하여 가장 먼저 1에 도착한 녀석에서 그 연산횟수의 cnt를 구하면 끝입니다.

 

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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

#include <iostream> #include<cstdio> #include <algorithm> #include <vector> #include <cmath> #include <queue> using namespace std; #define type_in in int n; bool a[1000001];   int bfs()//bfs로 풀기 {         int count=0;     queue<int> q;     q.push(n);//우선 q에 넣음     while(!q.empty())     {         int qsize=q.size();//큐사이즈만큼 반복하기위해         while(qsize--)         {             int t=q.front();//큐에있는것을 꺼내고             if(t==1)//1이면 카운트 리턴                 return count;             q.pop();//꺼냈으니 팝시켜야겠고             a[t]=1;//방문했따는것을 표시             if(t%2==0&&a[t/2]==0){//2의배수라면 2로나누고                 q.push(t/2);                 a[t/2]=1;             }             if(t%3==0&&a[t/3]==0){//3의배수라면 3으로나누고                 q.push(t/3);                 a[t/3]=1;             }             if(a[t-1]==0){//하나 빼주고                 q.push(t-1);                 a[t-1]=1;             }         }         count++;//큐사이즈만큼 다돌았다면 카운트는 증가     }     return count;//솔직히 이건 필요없음 }   int main(void) {     FILE *in =fopen("input.txt","r");     scanf("%d",&n);     printf("%d\n",bfs()); }   Colored by Color Scripter

cs

 

채점을 해보니 bfs방법이 더 빠르더군요

여러분도 한가지의 방법이아닌 여러가지의 방법이 생각난다면 되는지 해보시길 권장드립니다

궁금한점이나 모르는것이 있다면 언제든지 댓글을 이용해 주시길 바랍니다.