BOJ_7490 0 만들기3

• TOC {:toc}

이 글은 백준 온라인 저지의 7490번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.07.27 (Python)

import sys
sys.setrecursionlimit(10 ** 8)

def zero(n, nums, eqn):

    res = sum(nums)
    # 남은 수의 최댓값 (모든 수가 연결될 경우)
    left = 0
    for i in range(n + 1, N + 1):
        left = left * 10 + i
    # 남아있는 수가 없으면
    if not left:
        # 종료한다.
        return
    # 현재까지의 계산 결과에 left를 더한 값이 0이면
    if res + left == 0:
        # 남은 수를 모두 공백으로 연결한 뒤
        # 현재 식에 더해서 출력한다.
        print(f"{eqn}+{' '.join(str(left))}")
    # 현재까지의 계산 결과에 left를 뺀 값이 0이면
    elif res - left == 0:
        # 남은 수를 모두 공백으로 연결한 뒤
        # 현재 식에 빼서 출력한다.
        print(f"{eqn}-{' '.join(str(left))}")
    # 현재까지의 계산 결과의 절댓값이 left보다 크면
    # (남은 left를 빼거나 더해도 0을 만들 수 없기 때문에)
    elif abs(res) > left:
        # 종료한다.
        return

    # n을 1 증가시킨다.
    n += 1
    last = nums[-1]
    # 다음 n을 연결하는 경우
    if last >= 0:
        zero(n, nums[:-1] + [last * 10 + n], f"{eqn} {n}")
    else:
        zero(n, nums[:-1] + [last * 10 - n], f"{eqn} {n}")
    # 다음 n을 더하는 경우
    zero(n, nums + [n], f"{eqn}+{n}")
    # 다음 n을 빼는 경우
    zero(n, nums + [-n], f"{eqn}-{n}")

for _ in range(int(input())):
    N = int(input())
    zero(1, [1], "1")
    # 한 줄 건너뛴다.
    print()

아이디어 & 풀이

백트래킹 알고리즘을 재귀 용법으로 구현한다.

다음 수를 더하는 것과 빼는 것은 계산하기 쉽지만, 다음 수를 연결(이어 붙이는)하는 경우를 잘 처리해야 한다.

• 연속된 수의 처리를 편하게 하기 위해 현재까지 수의 총합이 아닌 현재까지 수의 리스트인 nums를 인자로 전달한다.
• 종결 조건에도 이를 잘 고려해야 한다.

함수 zero가 전달하는 인자는 다음가 같다.

• n: 현재 수, 1부터 입력값 N까지 증가한다.
• nums: 현재까지 계산된 수의 리스트.
• eqn: 현재까지의 계산식.

우선 재귀는 각 경우마다 인자를 다르게 전달한 함수를 작성해 구현한다.

• n은 전체적으로 1 증가시킨다.
• eqn은 현재 eqn과 증가한 n 사이에 각각 공백, +, -를 넣어 이은 문자열을 전달한다.
• nums는
  • 다음 n을 연결하는 경우, 마지막 원소 last에 증가한 n을 이은 값을 리스트로 만들어 마지막 원소를 제외한 리스트에 더한 리스트를 전달한다.
    • last가 양수인 경우 n을 더하고, 음수인 경우 n을 빼줘야 ‘이어진’값을 만들 수 있다.
  • 다음 n을 더하거나 빼는 경우 현재 nums에 증가한 n의 양수 / 음수값을 리스트로 만들어 더한 리스트를 전달한다.

숫자가 증가할수록 경우의 수가 3배씩 많아지므로 케이스를 drop 할 조건을 작성해야 한다.

남은 수로 만들 수 있는 최댓값이 현재까지의 계산 결과를 0으로 못 만드는 경우 drop 한다.

• 남은 수로 만들 수 있는 최댓값은 남은 숫자를 모두 연결해서 만든 수이다
  • e.g., 3, 4, 5가 남았을 경우 345
• nums의 원소를 더한 res가 위의 최댓값인 left보다 크면 종결한다.

다만 위의 경우 현재 nums의 마지막 원소에 남은 수를 연결해서 계산했을 때 0이 되는 케이스를 빠뜨리게 된다.

• 예를 들어 예제 입력 1의 1-2 3-4 5+6 7 케이스의 경우, n이 7일 때 nums가 [1, -2, 3, -45, 6], left가 7로 종결하는데
• 7을 6에 연결해 67을 만들어 더해 총합이 0이 되는 케이스에 접근하지 못하게 된다.
• 이 케이스를 챙기려면 nums가 [1, -2, 3, -45]이고 left가 67일 때, 이를 nums의 합과 left를 더해서 0이 되므로 이를 조건으로 걸러서 출력해야 한다.

정리하면,

• 우선, 남은 숫자가 없으면(left == 0) 종결한다.
• 남은 숫자를 모두 이은 값을 빼거나 더했을 때 조건을 만족하는 경우, 남은 원소로 eqn을 완성해 출력한다.
• 마지막 수를 더하거나 빼서 0을 완성할 수 있는 경우는 left가 1개일 때 같이 처리된다.
• 계산을 N까지 끝내기 전에 모든 경우를 출력하게 되므로 n이 N이고 res가 0일 때 출력하는 코드는 작성하지 않아야 한다.
• 위의 어떤 경우도 만족하지 않으면 n을 증가시킨 뒤 각 케이스(연결, 덧셈, 뺄셈)에 따라 함수를 다시 실행한다.

피드백

• 다른 풀이를 보니 중간에 drop 조건을 적지 않아도 제한 안에 해결할 수 있는 거 같다.

2022.03.12 (JS)

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().split("\n");

const [T, ...E] = input;
let res = [];

function main(N, n, num, sum, eqn) {
    if (n === N) {
        if (sum === 0) {
            res.push(eqn);
        }
        return;
    }

    n += 1;
    // blank
    main(N, n, num * 10 + n, sum - num + num * 10 + (num / Math.abs(num)) * n, `${eqn} ${n}`);
    // +
    main(N, n, n, sum + n, `${eqn}+${n}`);
    // -
    main(N, n, -n, sum - n, `${eqn}-${n}`);
}

for (let i = 0; i < T; i += 1) {
    const N = parseInt(E[i]);

    res = [];
    main(N, 1, 1, 1, "1");
    console.log(res.join("\n"));
    console.log();
}

피드백

• 아래 참고 답안처럼 배열로 관리해서 마지막에 sum을 계산하면 인자를 더 간단하게 전달하고도 해결할 수 있다.

참고 답안 1

def zero(n, now, eqn):
    if n == N:
        if sum(now) == 0:
            print(eqn)
        return

    n += 1
    last = int(str(now[-1]) + f"{n}")
    zero(n, now[:-1] + [last], f"{eqn} {n}")
    zero(n, now + [n], f"{eqn}+{n}")
    zero(n, now + [-n], f"{eqn}-{n}")


for _ in range(int(input())):
    N = int(input())
    zero(1, [1], "1")
    print()

아이디어 & 풀이

위의 풀이와 동일하지만, drop 조건을 없애고, 연결 연산을 할 때 last 계산을 더 간결하게 작성했다.

참고 답안 2

def zero(sum, sign, now, n, eqn):
    global N
    if n == N:
        sum += now * sign
        if sum == 0:
            print(eqn)
        return
    zero(sum, sign, now * 10 + (n + 1), n + 1, f"{eqn} {n + 1}")
    zero(sum + (sign * now), 1, n + 1, n + 1, f"{eqn}+{n + 1}")
    zero(sum + (sign * now), -1, n + 1, n + 1, f"{eqn}-{n + 1}")


for _ in range(int(input())):
    N = int(input())
    zero(0, 1, 1, 1, "1")
    print()

아이디어 & 풀이

연결, 덧셈, 뺄셈에 따라 인자를 다르게 전달한 재귀 함수를 작성해 구현한다.

각 인자가 의미하는 바는 다음과 같다.

• sum: 이전까지의 식을 계산한 값이다.
  • 더하거나 뺄 때는 현재 값을 sum에 계산해서 넘긴다.
  • 연결할 때는 sum 값은 그대로 유지하고 now에 이를 반영한다.
• sign: 현재 값(now)를 계산할 때 덧/뺄셈 여부를 결정하기 위한 부호이다.
  • 더할 때는 1
  • 뺄 때는 -1
  • 연결할 때는 이전 부호를 그대로 사용한다.
• now: 현재 값이다.
  • 더하거나 뺄 때는 다음 n 값인 n + 1을 전달한다.
  • 연결할 때는 현재 now 값에 다음 n + 1을 연결한 값을 전달한다.
• n: 현재 연산하는 숫자 값이다. 1부터 순차적으로 증가한다.
• eqn 현재 n까지 연산한 식이다. 조건을 만족할 때 출력한다.

현재 연산하는 값 n이 N과 같으면

• 마지막 연산(i.e., sum += now * sign)을 마무리한 뒤
• 연산 결과가 0인지 확인하고
• 0이면 eqn을 출력한다.

참고 답안 3

def zero(eqn, n):
    if n > N:
        if eval(eqn.replace(" ", "")) == 0:
            print(eqn)
        return

    zero(f"{eqn} {n}", n + 1)
    zero(f"{eqn}+{n}", n + 1)
    zero(f"{eqn}-{n}", n + 1)

for _ in range(int(input())):
    N = int(input())
    zero("1", 2)
    print()

아이디어 & 풀이

eval을 이용해 중간 과정을 간소화했다.

• 미리 연산 값을 구하지 않고, 연산식만 인자로 전달해 쌓아 나간다.
• 마지막 값까지 식을 완성했을 때 공백을 제거한 뒤 eval을 이용해 식의 결과를 구한다.
• 결괏값이 0이면 해당 식을 출력한다.