문제 정보



image

풀이

해당 문제는 min_dp 100개의 배열을 사용해서 해당 인덱스만큼의 성냥개비 개수로 만들 수 있는 최솟값을 배열에 넣었다.
이후, 성냥개비 개수가 주어지면 최솟값과 최댓값을 찾아야 하는데, 최댓값은 다음과 같은 알고리즘으로 쉽게 풀 수 있었다.

[ 최댓값 구하기 ]

성냥개비 단 두개로 숫자 1을 만들어서 자릿수를 높여야 한다.
그러므로 만약 성냥개비 개수가 짝수일 경우, 성냥개비 숫자 / 2 한 만큼 1을 붙여주면 된다.
ex) 성냥개비 개수 = 8개일 경우 -> 최댓값 1111
성냥개비 개수가 홀수일 경우, 1로 모든 성냥개비를 사용해서 채울 수 없으므로 가장 적은 개수로 만들 수 있는 가장 큰 수인 7을 앞에 붙여주고 남은 성냥개비로 1을 붙여준다
ex) 성냥개비 개수 = 7개일 경우 -> 최댓값 711

[ 최솟값 구하기 ]

IMG_1990DD8FCF22-1
최솟값 구하기는 아까 말했듯이 dp를 이용하여 풀었다.
위와 같이 규칙을 찾기 위해 계속 표를 작성해보았는데, 2 ~ 8까지는 직접 개수를 세서 적어놨고, 9부터는 점화식을 이용하여 dp 이전 원소들과 2 ~ 8 개수를 사용하여 최솟값을 구할 수 있었다.
예를 들어, 성냥개비 10개로 만들 수 있는 최솟값을 구하려면 다음과 같은 알고리즘을 거쳐야한다.

  • 8개로 만들 수 있는 최솟값 10, min_dp[2] 배열 값 1을 나열 -> 101
    -> 가장 처음에 보는 경우가 대부분 최댓값이므로, min값 갱신 초기화값으로 넣어준다
  • 7개로 만들 수 있는 최솟값 8, min_dp[3] 배열 값 7을 나열 -> 87
  • 6로 만들 수 있는 최솟값 6, min_dp[4] 배열 값 4을 나열 -> 64
  • 5개로 만들 수 있는 최솟값 2, min_dp[5] 배열 값 2을 나열 -> 22
  • 4개로 만들 수 있는 최솟값 4, min_dp[6] 배열 값 6을 나열 -> 46
  • 3개로 만들 수 있는 최솟값 7, min_dp[7] 배열 값 8을 나열 -> 78

이것을 코드화하면 다음과 같다

 // 9부터 점화식 적용
    for i in 9...100 {
        // 2번째 전 원소로 만든 숫자 뒤에 숫자 1을 붙인다 ex: i == 9 일 때, dp[7]*10 + dp[2] = 81
        // 초기값으로 가장 클 것 같은 수를 넣어주고, 계속 비교해본다
        dp[i] = dp[i-2]*10 + minNum[2]
        for j in 3...7 {
            // 더해서 i를 만들 수 있는 조합으로 비교하여 최솟값을 찾는다
            dp[i] = min(dp[i], dp[i-j]*10 + minNum[j])
        }
    }

코드

import Foundation

// 최솟값: 3을 입력받으면 dp 배열 앞부터 돌면서 3인 값 출력

// 2 ~ 8 까지의 수는 미리 minNum 배열에 넣어놓는다. -> 점화식에서 일의 자리 수로 사용
var minNum: [Int] = [0, 0, 1, 7, 4, 2, 0, 8, 10]

// 해당 idx만큼의 성냥개비가 있을 때 만들 수 있는 최솟값을 넣어준다
var dp: [Int] = Array(repeating: 0, count: 101)
func findMin() {
    
    // 2 ~ 8 까지는 minNum 값이 최솟값임
    for i in 2...8 {
        dp[i] = minNum[i]
    }
    
    // 숫자는 0으로 시작할 수 없다는 조건이 없으므로 6개일 때 만들 수 있는 최솟값은 0이 아니라 그 다음 작은 수 6이 되어야 한다
    dp[6] = 6
    
    // 9부터 점화식 적용
    for i in 9...100 {
        // 2번째 전 원소로 만든 숫자 뒤에 숫자 1을 붙인다 ex: i == 9 일 때, dp[7]*10 + dp[2] = 81
        // 초기값으로 가장 클 것 같은 수를 넣어주고, 계속 비교해본다
        dp[i] = dp[i-2]*10 + minNum[2]
        for j in 3...7 {
            // 더해서 i를 만들 수 있는 조합으로 비교하여 최솟값을 찾는다
            dp[i] = min(dp[i], dp[i-j]*10 + minNum[j])
        }
    }
}

// 최댓값: 홀수인 경우 -> 3개로 7 구성하여 맨 앞자리 만들고 나머지 2개로 1 구성하여 채운다 ex: 7 -> 711
//       짝수인 경우 -> 2개로 나눈 값을 1로 붙인다
func findMax(_ num: Int) {
    var result = Array(repeating: 1, count: num / 2)
    if num % 2 != 0 {
        result[0] = 7
    }
    print(result.map{String($0)}.joined(separator: ""))
    
}

findMin()
for _ in 1...Int(readLine()!)! {
    let N = Int(readLine()!)!
    
    // 예외 케이스 출력
    if N == 2 {
        print(1, 1, separator: " ")
    }
    else if N == 3 {
        print(7, 7, separator: " ")
    }
    else {
        print(dp[N], terminator: " ")
        findMax(N)
    }
}