https://www.acmicpc.net/problem/3687
3687번: 성냥개비
각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다.
www.acmicpc.net
[난이도] Gold2
[유형] DP
[풀이]
최솟값은 DP, 최댓값은 규칙성을 이용
#include <iostream> #include <string> #include <algorithm> using namespace std; int tc,N; long long dp[101]={0,0,1,7,4,2,6,8,10,}; int main(){ cin >> tc; for(int i=9;i<101;i++){ dp[i]=9e20; for(int j=2;j<=7;j++){ long long v = dp[i-j]*10; if(j!=6) v+=dp[j]; dp[i]=min(dp[i],v); } } while(tc--){ cin >> N; string maxv; cout << dp[N]; if(N%2==0) { for(int i=0;i<N/2;i++) maxv+='1'; } else{ maxv+='7'; for(int i=0;i<N/2-1;i++) maxv+='1'; } cout << ' ' << maxv << '\n'; } }
https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/3687.cpp
'Problem-Solving > BOJ' 카테고리의 다른 글
| [BOJ/백준][Gold5] 11509 : 풍선 맞추기 (C++) (0) | 2022.03.27 |
|---|---|
| [BOJ/백준][Gold5] 17836 : 공주님을 구해라! (C++) (0) | 2022.03.27 |
| [BOJ/백준][Gold2] 1781 : 컵라면 (C++) (0) | 2022.03.27 |
| [BOJ/백준][Gold2] 1445 : 일요일 아침의 데이트 (C++) (0) | 2022.03.27 |
| [BOJ/백준][Gold2] 14725 : 개미굴 (C++) (0) | 2022.03.27 |