[BOJ 3687] 성냥개비

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

3687번: 성냥개비

 

- 문제 요약

 

성냥개비로 나타낸 0~9까지의 숫자

십진수를 성냥개비로 표현하는 방법은 위와 같다.

정수 N이 첫 번째 줄에 주어지고, 2~N+1번째 줄에 테스트케이스 별로 성냥개비의 수가 주어진다.

이때, 각 줄에 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 큰 수를 출력하시오.

 

 

- 알고리즘 정리

 

최대 값을 구할 때는 테스트케이스를 참고해 봤습니다.문제에서 주어지는 입력과 출력은 아래와 같습니다.

[입력]
4
3
6
7
15
[출력]
7 7
6 111
8 711
108 7111111

성냥개비 2개로 만들 수 있는 최댓값은 1, 3개로 만들 수 있는 최대값은 7입니다.

그래서 입력으로 들어오는 수가 홀수면 앞에 7이 붙고 뒤에 1이 쭈르륵, 짝수면 그냥 1이 쭈르륵 인 수가 출력됩니다.

( ex)  홀수 : 711111, 짝수 : 11111111 )

최댓값 만드는 부분은 증명 안 하고 반쯤 찍었는데 맞았네요 ㅎ;;

 

최소 값을 구할 때는 주어지는 성냥개비의 개수가 0~8일 경우에 직접 손으로 그려가며 답을 배열에 넣어줬습니다.

9부터는 점화식을 세워서 풀었는데, 성냥개비의 수를 나눠서 최솟값을 만드는 형식으로 세웠습니다. +) 일반화

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

int t,n,arr[9]={0,0,1,7,4,2,0,8,10};
long long mn[101];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	for(int i=1;i<9;i++){
		mn[i]=arr[i];
	}
	mn[6]=6;
	for(int i=9;i<=100;i++){
        mn[i]=mn[i-2]*10+arr[2];
        for(int j=3;j<8;j++){
            mn[i]=min(mn[i],mn[i-j]*10+arr[j]);
        }
    }
	cin>>t;
	while(t--){
		cin>>n;
		cout<<mn[n]<<" ";
		while(n){
            if(n%2!=0){
                cout<<7;
                n-=3;
            }
            else{
                cout<<1;
                n-=2;
            }
        }
        cout<<'\n';
	}
}

코드 제출 결과

처음 틀렸을 때, 왜 틀렸나 봤더니 mn 배열 수가 int 범위를 벗어나더라고요...

그래서 long long으로 고치고 바로 AC 받았습니다 :D