2019 Google Code Jam QR 1. Foregone Solution

2019년 구글 코드잼 예선전(Qualification Round) 1번 문제를 풀어보겠습니다. 문제는 https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/0000000000088231에서 직접 풀어서 제출해볼 수 있습니다. 문제 내용은 아래와 같습니다.

---

Someone just won the Code Jam lottery, and we owe them N jamcoins! However, when we tried to print out an oversized check, we encountered a problem. The value of N, which is an integer, includes at least one digit that is a 4... and the 4 key on the keyboard of our oversized check printer is broken.

Fortunately, we have a workaround: we will send our winner two checks for positive integer amounts A and B, such that neither A nor B contains any digit that is a 4, and A + B = N. Please help us find any pair of values A and B that satisfy these conditions.

---

이미지 출처: https://www.af.mil/News/Photos/igphoto/2000267092/

문제가 주절주절 깁니다. 해석해 보면 다음과 같습니다.

---

누군가 코드잼 복권에 당첨되었고 우리(주최 측)는 N 잼 코인을 상금으로 주저야 합니다. 그런데 상금을 거대 수표로 출력하려고 하는데 문제가 있네요. 상금은 N이라 하고 정수입니다. 최소 하나 이상의 숫자 4를 포함하고 있습니다. 그런데 프린터기의 4가 고장 났습니다.

다행히 차선책이 있습니다. 두 개의 수표로 나누는 거죠. 정수 두 개로 나누고 금액은 A와 B라고 합시다. A와 B는 4를 포함하지 않습니다. A와 B를 합하면 상금 N이 됩니다. A와 B를 구해주세요.

---

요약해 보면 숫자(정수) 4가 포함된 상금을 주려고 하는데 4를 출력할 수 없는 상황입니다. 그래서 4가 들어있지 않은 수로 상금을 2번에 나눠서 지급한다는 말입니다.

4원의 상금을 준다면 2원씩 두 번 나눠서 주면 되겠죠. 1원과 3원으로 나눠서 줄 수도 있습니다. 상금의 크기가 커질수록 나눠서 줄 수 있는 경우의 수도 늘어날 거 같습니다.

입력값과 출력 값의 예제를 보겠습니다. 먼저 입력값입니다.

3
4
940
4444

첫째줄은 테스트 케이스 개수 T를 의미합니다. 구현 방법에 따라 다르겠지만 이 값은 무시해도 문제는 풀 수 있습니다. 다음 줄부터가 상금입니다. 상금 A, B로 나눠야 합니다. 나눈 상금에는 숫자 4가 있으면 안 됩니다.

출력 값 예제를 보겠습니다.

Case #1: 2 2
Case #2: 852 88
Case #3: 667 3777

4가 포함되지 않네요. 두 숫자를 합치면 원래의 상금이 됩니다. 앞서 설명했지만 답은 여러 가지가 나올 수 있습니다.

이미지 출처: https://pixabay.com/ko/illustrations/%EB%AC%B8%EC%A0%9C-%EB%AC%B8%EC%A0%9C-%ED%95%B4%EA%B2%B0-%EB%B0%A9%EB%B2%95-%EC%86%94%EB%A3%A8%EC%85%98-98377/

문제 해결 방법을 알아봅시다. 단순하게 생각해 보면 상금 금액에서 1씩 빼면서 상금 A, B를 구하고 4가 없는지 확인하면 됩니다. 940 같은 경우 빠르게 답을 찾을 수 있습니다. 1과 939가 되겠네요. 하지만 4444는 시간이 좀 걸리겠네요. 1을 빼면 1과 4443이 되겠네요. 최소한 첫자리 4가 없어질 때까지 반복해야 합니다. 상금 A, B가 모두 4가 없는 값이 나오려면 좀 더 시간이 걸리겠네요. 언젠가 답이 나오긴 하겠지만 숫자가 커지면 그만큼 시간이 더 오래 걸리게 됩니다.

위에서 설명한 방법을 코드로 구현해 보면 다음과 같습니다.

tc = int(input())


def solve(n):
    for i in range(1, n):
        a = i
        b = n - a

        str_a = str(a)
        str_b = str(b)
        if '4' not in str_a and '4' not in str_b:
            return str_a + " " + str_b


for t in range(1, tc+1):
    n = int(input())
    ans = solve(n)
    print("Case #" + str(t) + ": " + ans)

테스트해 보면 아래처럼 출력됩니다. 4가 안 보이는 거로 보아 답은 잘 나오는 거 같습니다.

Case #1: 1 3
Case #2: 1 939
Case #3: 505 3939

 

이 코드를 제출해 보면 아래처럼 시간이 초과되었다고 나옵니다.

이미이 출처: https://openclipart.org/detail/181401/distressed-man

어떻게 하면 좋을까요? 앞서 A, B를 먼저 구하고 4가 포함되어있는지 찾아보았는데요. 그렇다면 처음부터 상금에서 4를 다른 숫자로 바꾸고 A라고 합니다. 상금에서 A를 빼서 B를 구하면 될 거 같지 않나요? A가 상금보다 커지면 안 되니 4보다 작은 수로 바꾸면 될 거 같습니다. 다만 0은 안 되겠네요. 0으로 바꾸면 B에 4가 생길 테니 말이죠.

자 맞는지 검증해 보려면 코드로 구현해 봐야겠죠?

tc = int(input())

def solve(n):
    a = int(str(n).replace('4', '3'))
    b = n - a
    return str(a) + " " + str(b)


for t in range(1, tc+1):
    n = int(input())
    ans = solve(n)
    print("Case #" + str(t) + ": " + ans)

짝짝짝. 통과했습니다. 풀고 보니 입력값을 정수로 바꿨다가 다시 문자열로 바꾸는 부분을 좀 더 최적해해 볼 수 있을 거 같습니다. 잘 찾아보면 좀 더 최적화할 방법이 있을 거 같습니다. 하지만 이런 개선은 대세에 큰 영향을 주긴 어렵습니다. 더 획기적인 알고리즘을 찾아내어서 더 빠른 해결방법을 찾을 수도 있겠습니다. 하지만 문제는 더 남아 있고 시간은 제한되어 있으니 일단 다른 문제를 먼저 풀어 보는 게 좋을 수도 있습니다.

ps. 내일은 드디어 구글 코드잼 2020 Qualification Round가 열리는 날입니다. 한번 참가해 보고 싶으신 분들은 빨리 참가 신청을 해 보시기 바랍니다 :)

구글코드잼 Qualification Round 2020 신청하기