백준 3686 성냥개비 Python 3

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

3687번: 성냥개비

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ3687.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

T = int(input())
answer = []
dp = [0, 0, [1, 1], [7, 7], [4, 11], [2, 71], [6, 111], [8, 711], [10, 1111], [18, 7111], [22, 11111]]
p = ['8', '10', '18', '200', '20', '28', '68']
for _ in range(T):
    n = int(input())
    if n < len(dp):
        answer.append(dp[n])
        continue
    if n%2==0:
        max = '1'*(n//2)
    else:
        max = '7' + '1'*((n-3)//2)
    pivot = n%7
    if pivot == 3:
        min =  p[pivot] + '8'*(n//7-2)
        answer.append([int(min), int(max)])
        continue
    #pivot: 0, 1, 2, 4, 5
    min = p[pivot]+'8'*(n//7-1)
    answer.append([int(min), int(max)])
for i in range(len(answer)):
    print(answer[i][0], answer[i][1])

---

풀이 과정

풀이 시간 1시간 50분

규칙을 찾아서 푸는 문제이다. n = 2 ~ n = 24까지 직접 구해보고 나서 규칙을 찾을 수 있었다.

 

최댓값은 자릿수를 가장 크게 만드는 것이 핵심이다. 성냥개비 2개로 1을 만들 수 있기 때문에 1을 최대한 많이 만드는게 자릿수를 가장 크게 만들 수 있는 방법이다.

예를 들면, n = 10인 경우 최댓값은 1을 5개 만든 1111이다.

n = 11인 경우에는 1을 5개 만들 수 있지만 남은 성냥 1개로는 어떤 숫자도 만들 수 없다. 문제는 모든 성냥을 다 써서 만들 수 있는 수를 구하라고 했으니, 이 경우 1을 4개 만들고 남은 성냥 3개로 7을 만들어야 한다. 즉, 최댓값은 7111이다.

계속해서 구해보면 다음과 같다.

n = 12 -> 111111

n = 13 -> 711111

n = 14 -> 1111111

n = 15 -> 7111111

자, 규칙을 찾았는가?

바로 n이 짝수인 경우, n/2개의 1을 만들 수 있기 때문에 최댓값 = '1'*(n//2)이다.

n이 홀수인 경우, 맨 앞자리는 성냥 3개로 만들 수 있는 7, 나머지는 1을 만들면 되므로 최댓값 = '7' + '1'*((n-3)//2)이다.

 

그렇다면, 최솟값을 구해보자.

나는 규칙을 찾기 위해 n = 8 ~ n = 24까지 만들어봤다.

n	최솟값
8	10
9	18
10	22
11	20
12	28
13	68
14	88
15	108
16	188
17	200
18	208
19	288
20	688
21	888
22	1088
23	1888
24	2008

자, 규칙이 보이는가?

n을 8로 나눈 나머지 값을 기준으로 뒤에 8이 붙는 걸 알 수 있다.

이때, 주의해야 할 점은 n = 10인 경우는 최솟값 = 22로 예외이다.

n = 10이 아닌 경우는 뒤에 계속 8을 붙여주면 되는 것이다.

 

즉, 다음과 같다.

n%7	최솟값(n)
1	10(8), 108(15), 1088(22)
2	18(9), 188(16), 1888(23)
3	200(17), 2008(24), 20088(31)
4	20(11), 208(18), 2088(25)
5	28(12), 288(19), 2888(26)
6	68(13), 688(20), 6888(27)
0	88(14), 888(21), 8888(28)

따라서, n = 10인 경우의 예외를 처리하기 위해  n%7 = 3인 경우만 잘 처리해서 값을 구해주면 된다!

 

T = int(input())
answer = []

#dp[n] = [최솟값, 최댓값]
dp = [0, 0, [1, 1], [7, 7], [4, 11], [2, 71], [6, 111], [8, 711], [10, 1111], [18, 7111], [22, 11111]]

#p[n%3]: 0, 1, 2, 4, 5 -> 최솟값 =  p[n%3] + '8'*(n//7-1)
#p[n%3] = 3 -> 최솟값 = p[n%3] + '8'*(n//7-2)
p = ['8', '10', '18', '200', '20', '28', '68']

for _ in range(T):
    n = int(input())
    
    #n이 10 이하인 경우
    if n < len(dp):
        answer.append(dp[n])
        continue
        
    #최댓값 구하기
    #n이 짝수인 경우
    if n%2==0:
        max = '1'*(n//2)
    #n이 홀수인 경우
    else:
        max = '7' + '1'*((n-3)//2)
        
    #최솟값 구하기
    pivot = n%7
    if pivot == 3:
        min =  p[pivot] + '8'*(n//7-2)
        answer.append([int(min), int(max)])
        continue
    #pivot: 0, 1, 2, 4, 5
    min = p[pivot]+'8'*(n//7-1)
    answer.append([int(min), int(max)])
    
for i in range(len(answer)):
    print(answer[i][0], answer[i][1])
#시간복잡도 = O(T), 공간복잡도 = O(T)