백준 3687 - 성냥개비 [Python]

www.acmicpc.net/problem/3687

3687번: 성냥개비

Greedy

 

 

큰 수는 111..., 7111... 의 형태이고, 작은 수는 ???88888...의 형태이다. 노트에 몇번 끄적이다 보면 보인다.

 

큰 수는 홀수 짝수,

작은수는 7로 나눈 나머지에 따라 케이스를 나누어 풀어주면 된다

import sys
input = sys.stdin.readline
 
d = [0,0,1,7,4,2,6,8,10,18,22]
 
def getMax(n):
    ret = [1 for i in range(n//2)]
    if n&1: ret[0]=7
    return ret
 
def getMin(n):
    ret = [8 for i in range((n+6)//7)]
    if n%7==1: ret[0]=1;ret[1]=0
    if n%7==2: ret[0]=1
    if n%7==3: ret[0]=2;ret[1]=0;ret[2]=0
    if n%7==4: ret[0]=2;ret[1]=0
    if n%7==5: ret[0]=2
    if n%7==6: ret[0]=6
    return ret
 
for _ in range(int(input())):
    N = int(input())
    if N<11:
        print(d[N],end=" ")
    else:
        print(*getMin(N),sep='',end=' ')
    print(*getMax(N),sep='')