Mystika+Algorithm

'2016/09/01'에 해당되는 글 1건

  1. BOJ 1660 - 캡틴 이다솜

BOJ 1660 - 캡틴 이다솜

알고리즘/동적 계획법

문제

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


풀이

주어진 N을 가지고 사면체를 최소로 만들어 N을 0으로 만드는것이 목표이다. 다르게 말하자면 그냥 동전 교환 문제이다.

만약 항상 한 개의 사면체를 만들만큼만 N이 주어진다면 좋겠지만 탐욕법으로 풀 수 있겠지만 동전 1문제 처럼 이 문제는 탐욕적으로 풀 수 없는 케이스가 있다.

예를들어 N이 50일때 탐욕법을 이용해 풀면 $45+3+1+1$가 답이되어 4개가 답이 되지만 실제로는 $20+20+10$로 3개가 최소이다.

동전 문제와는 다르게 이 문제는 사면체 수가 주어지지 않는데 이 값들은 여러번 사용할 것이므로 사면체 수를 구해놓고 배열에 저장해놓는다면 시간을 매우매우 줄일수 있다.

만약 입력값이 작다면 그냥 풀어도 되지만 문제 최대 입력이 300,000이고 이 값이 들어왔을때 메모이제이션을 적용하지 않는다면 시간 초과가 발생하게 된다. 메모이제이션은 이 문제에서 원하는 DP[N] = N으로 만들수 있는 최소 사면체 수로 적용하면 된다.


PS 처음에는 Top-down으로 풀려고 했는데 어쩌다보니 Bottom-up 풀이가 되어버렸다. 나중에 Top-down으로도 다시 짜봐야겠다.

//mincost[n] = n으로 만들수 있는 최소 사면체 수 //sum[n] = n 사이즈 사면체를 만드는데 필요한 대포알의 수

#include <stdio.h> #define INT_MAX 98765431 int sum[130]={0},mincost[300001]={0}; int min(int a, int b){ return a<b?a:b; } int solve(int ball, int pos,int count){ if(ball<0) return INT_MAX; if(mincost[ball]) return mincost[ball]; if(pos<1) return INT_MAX; if(ball == 0) return count; mincost[ball] = min(solve(ball-sum[pos],pos,count)+1, solve(ball,pos-1,count)); return mincost[ball]; } int main(){ int i=0,n,maxp; scanf("%d",&n); while(++i){ sum[i] = i*(i+1)*(i+2)/6; if(sum[i] >= 300000) break; } maxp=i-1; for(i=1;i<=n;i++){ solve(i,maxp,0); } printf("%d",mincost[n]); }


저작자 표시 비영리 변경 금지
신고