백준 23565번: 1, 2, 3, 4 [Python]

작성일 | In
플래티넘 I 플래티넘 I

문제

1, 2, 3, 4
1원, 2원, 3원, 4원짜리 동전의 개수가 주어지면, 0을 포함해 만들 수 있는 금액의 경우의 수를 구하는 문제입니다.

풀이

$a, b, c, d \leq 10^{17}$이라 $O(N^4)$은 물론이고 $O(N)$에도 풀 수 없습니다. 그렇다면 $O(1)$에 풀어야 한다는 것을 간접적으로 알 수 있습니다.
그래서 저는 이 문제의 제한을 보고 그만 정신을 잃고 말았습니다…

배수 관계인 경우

학교에서 배우는 이런 문제는 보통 동전의 액수가 배수 관계로 주어집니다. 그러면 계산이 간단해지기 때문입니다. 예를 들어, $n$원짜리 동전과 $kn$원짜리 동전이 주어진다고 합시다. 이때 $n$원짜리 동전의 총합이 $kn$원 이상이라면, 그러니까 $n$원짜리 동전이 $k$개 이상 있다면 $kn$원짜리 동전을 모두 $n$원짜리 동전으로 바꾸고 문제를 풀어도 답이 똑같습니다. 만약 위 조건을 만족하지 못한다면
n원짜리 동전의 개수 $\times$ kn원짜리 동전의 개수 $+\ 1$이 답이 됩니다.

조금 응용하면 $a \geq 2$일 때, 혹은 $b \geq 2$일 때의 답을 구할 수 있습니다.

$a \geq 2$일 때

$b, c, d$의 값에 따라 나뉩니다.

$b \geq 1$일 때

$1$과 $2$를 교차로 쓰면 $a + 2b$까지의 모든 음이 아닌 정수를 표현 할 수 있습니다. 따라서 $2$를 모두 $1$로 바꿔도 됩니다.

$c \geq 1$일 때

$b \geq 1$일 때와 같은 이유로, $3$를 모두 $1$로 바꿔도 됩니다.

$d \geq 1$일 때

더이상 $1$이 $4$까지 표현해주지 못하므로, $b = 0$이고 $c = 0$이면서 $d \geq 1$이면 답은
$(a + 1) * (d + 1)$이 됩니다.
(0개를 고르는 경우도 포함해야 하기 때문에 1을 더합니다.)

정리하면 아래와 같습니다.

$d \geq 1,\ b = 0, c = 0$이면 $(a + 1) \times (d + 1)$
그렇지 않으면 $a + 2b + 3c + 4d + 1$

그렇지 않은 경우

이 부분이 풀이의 90%를 차지한다고 생각하시면 됩니다. 여기부터는 규칙 찾는 노가다의 과정에 가깝습니다.
3, 4를 1, 2로 바꿀 수 없거나, 4로 만든 수가 3과 겹치는 경우가 발생합니다.
이러한 경우를 세분화하여 나눠줍니다. 이 문제의 태그에 많은 조건 분기가 붙어있는 이유이기도 합니다.

$a = 1,\ b = 1,\ c \geq 1,\ d \geq 1$일 때

$a + 2b + 3c + 4d + 1$입니다.
1, 2, 3, 4의 협동으로 모두 1로 바꾸고 답을 구할 수 있습니다.

4개중 하나만 양수일 때

당연히 양수인 수 + 1만큼이 답이 됩니다. (= $a + b + c + d + 1$)

$a$와 $b$만 양수이거나 $a,\ b$중 하나가 양수이고 $c,\ d$중 하나가 양수일 때

큰 수를 작은 수로 바꿀 수 없으므로 그냥 구해주면 됩니다. $(a + 1) \times (b + 1) \times (c + 1) \times (d + 1)$입니다.

$a = 0,\ b = 0$이고 $c,\ d$는 양수일 때

이 문제의 난이도를 끌어올린 주범입니다. 이 케이스를 해결하는 방법은 직접 해보는 것입니다. 진짜 손으로 해보긴 좀 그러니까 컴퓨터의 힘을 빌리면 됩니다. python의 set은 순서를 보장하기 때문에, 브루트포스 알고리즘으로 직접 해보면 편합니다. python idle image1 (python의 range(n)은 0부터 n미만까지를 의미합니다.)
$c = 1$이고 $d = 1$일 때 당연하게도 4입니다.

python idle image2 $c = 1$혹은 $c = 2$혹은 $d = 1$이라면 위와 비슷합니다. 3과 4로 만들 수 있는 수가 겹치지 않아서 그냥 계산하면 됩니다. $(c + 1) * (d + 1)$

python idle image3 그렇지 않다면, 위와 같습니다. 3과 4로 만들 수 없는 1, 2, 5를 제외하고 모든 수를 만들 수 있습니다.
$0$부터 $3c + 4d$까지 $1,\ 2,\ 5,\ 3c + 4d - 1,\ 3c + 4d - 2,\ 3c + 4d - 5$를 제외하고 모두 만들 수 있습니다.
따라서 $3c + 4d - 5$이 답이 됩니다.
-6이 아닌 이유는 0을 포함해야 하기 때문입니다.

4개중 하나만 0인경우

거의 다 왔습니다. 마무리를 잘 지어봅시다.

$a = 0$인 경우

$b \geq 2$인 경우는 처리헀으므로 $b = 1$입니다.
아까 3과 4만 있던 경우와 달리 2가 추가되었기 때문에
$0$부터 $2b + 3c + 4d$까지 $1,\ 2b+3c+4d-1$을 제외하고 모두 만들 수 있습니다.
따라서 $2b + 3c + 4d - 1 = 1 + 3c + 4d$가 답이 됩니다.

$b = 0$인 경우

$c = 1$인 경우

python idle image4 1과 3이 합쳐져 다양한 수를 만들지만 2는 만들지 못합니다. 4의 배수가 아닌 2를 제거해줘야 합니다.
$0$부터 $a + 3c + 4d$까지 2의 배수는 $(a + 3c + 4d)/2$개이고, 그중 4의 배수는 $(a + 3c + 4d)/4$개입니다.
그럼 우리가 제외해야할 2의 개수는 $(a + 3c + 4d)/4$개입니다.
그런데 $a + 3c = 4$이므로 $d + 1$개입니다.
$0$부터 $a + 3c + 4d$까지 $d + 1$개를 제거해주면
$a + 3c + 4d + 1 - d - 1 = a + 3c + 3d = 4 + 3d$입니다.

그렇지 않은 경우

$a + 3c + 4d$까지 $2, a+3c+4d-2$를 제외하고 모두 만들 수 있습니다.
따라서 $3c + 4d$입니다.

$c = 0$인 경우

바꾸는 거나 겹치는 것이 없으므로 그냥 경우를 계산해주면
$(a + 1) \times (b + 1) \times (d + 1)$
$= 4 * d + 4$

$d = 0$인 경우

$0$부터 $a + 2b + 3c$까지 만들 수 있습니다.
따라서 $(a + 1) \times (b + 1) \times (c + 1)$

그 외

$a+b+c+d = 0$인 경우이므로 1이 답이 됩니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import sys

input = lambda: sys.stdin.readline().rstrip()

T = int(input())

for i in range(T):
    a, b, c, d = map(int, input().split())
    if a >= 2:
        if (b + c == 0) and (a < 4):
            print((a + 1) * (d + 1))
        else:
            print(a + 2 * b + 3 * c + 4 * d + 1)
    elif b >= 2:
        b += 2 * d
        if a == 1:
            print(a + 2 * b + 3 * c + 1)
        elif c >= 1:
            print(2 * b + 3 * c - 1)
        else:
            print(b + 1)

    else:
        if (a == 1) and (b == 1) and (c >= 1) and (d >= 1):  # 모두 양수면
            print(a + 2 * b + 3 * c + 4 * d + 1)
        elif (a == 0) + (b == 0) + (c == 0) + (d == 0) == 3: # 하나만 양수면
            print(a + b + c + d + 1)

        elif ((a == 0) + (b == 0) + (c == 0) + (d == 0) == 2) and (c * d == 0): # 두개만 양수면
            print((a + 1) * (b + 1) * (c + 1) * (d + 1))
        elif (c >= 1) and (d >= 1) and (a + b == 0):  # c, d만 양수면
            if c == 1 or c == 2 or d == 1:
                print((c + 1) * (d + 1))
            else:
                print(3 * c + 4 * d - 5)

        elif (a == 0) and (b and c and d):  # a만 0이면
            print(1 + 3 * c + 4 * d)
        elif (b == 0) and (a and c and d):  # b만 0이면
            if c == 1:
                print(4 + 3 * d)
            else:
                print(3 * c + 4 * d)
        elif (c == 0) and (a and b and d):  # c만 0이면
            print(4 * d + 4)
        elif (d == 0) and (a and b and c):  # d만 0이면
            print(3 * c + 4)
        else:
            print(1)

여담

6 hour
이 문제 푸는데 6시간 정도 걸렸던걸로 기억합니다.
밥먹고 쉬고 하는 시간 빼면 3시간정도 되겠네요. 밥먹으면서도 머릿속에서 계속 1, 2, 3, 4 생각하면서 맞왜틀?맞왜틀?시전하다가 제가 얼마나 작은 존재인지 깨닫고 메모장을 잡고 늘어졌습니다. 답지의 도움 하나도 없이 푼 문제 중 가장 어려운 문제라 제게 의미가 있는 것 같네요. 끈기 하나로 문제 잡고 늘어지는것도 재밌는 것 같습니다.

백준 23565번: 1, 2, 3, 4 [Python]