[백준 (BOJ)] 1629 곱셈 - 스위프트(Swift)

[Gold III] 크게 만들기 - 2812

문제 링크

성능 요약

메모리: 86700 KB, 시간: 80 ms

분류

자료 구조, 그리디 알고리즘, 스택

문제 설명

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

출력

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

 

풀이

i)

for문을 반복하여 제곱만큼 곱하면서, 만약 c보다 크거나 같은 값이 나타나면 먼저 나머지를 구함으로 Int의 크기에 대해 해결해주고자 하였습니다.

 

따라서 코드는 다음과 같습니다.

let input = readLine()!.split(separator: " ").map { Int($0)! }
let (a, b, c) = (input[0], input[1], input[2])
var ans = a

for _ in 1..<b {
    ans *= a
    if ans >= c {   // c보다 크거나 같다면
        ans = ans % c
    }
}
print(ans)

→ 시간 초과

 

사실 해당 문제는 정수의 범위도 생각해주어야 하지만, 시간 초과에 대해 생각하는 것이 관건이었습니다.

 

ii)

따라서 해당 문제는 정복 분할을 통해 해결할 수 있었습니다.

 

정복 분할의 문제같은 경우 초기 케이스(base case)를 설정하고, 경우의 수를 분할하여 문제를 해결하는 방식입니다.

 

해당 문제는 짝수인 경우와 홀수인 경우로 나누어서 해결할 수 있습니다.

짝수인 경우는 제곱 승을 반으로 나눈 뒤, 각각 계산한 것을 곱해주면 해결할 수 있습니다.

홀수인 경우는 제곱 승을 반으로 나눈 뒤, 각각 계산한 것을 곱한 뒤 값을 추가적으로 곱해주면 해결할 수 있습니다.

 

예를 들어, 10 11 12를 그림을 통해 보여드리겠습니다.

예시

다음과 같이 재귀 호출이 반복되어 값을 도출해낼 수 있습니다.

 

다음은 코드입니다.

let input = readLine()!.split(separator: " ").map { Int($0)! }
let (a, b, c) = (input[0], input[1], input[2])

func divideConquer(_ b: Int) -> Int {
    if b == 0 { return 1 }  // b가 0이면 의미가 없음
    if b % 2 == 0 { // 짝수인 경우
        let divNum = divideConquer(b / 2)
        
        return divNum % c * divNum % c
    } else {    // 홀수인 경우
        let divNum = divideConquer((b-1) / 2)
        
        return divNum % c * divNum % c * a % c
    }
}
print(divideConquer(b))

 

재귀 함수의 경우 예전부터 계속 어려운데.. 더욱 더 공부를 해야할 것 같습니다.