• TOC {:toc}

이 글은 백준 온라인 저지의 1495번 문제를 풀이한 것을 모아놓은 글입니다.

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

2021.06.21 (Python)

메모리 시간 코드 길이
29200 KB 76 ms 321 B
단계 시작 시각 끝난 시각 걸린 시간
문제 이해 22:43:24 22:45:21
풀이 생각 22:46:46 22:54:49
코딩 10:56:28 11:04:52
디버깅 11:06:09 11:07:28 
N, S, M = map(int, input().split())
D = list(map(int, input().split()))
V = set([S])

for diff in D:
    tmp = set([])
    for v in V:
        if v + diff <= M:
            tmp.add(v + diff)
        if v - diff >= 0:
            tmp.add(v - diff)
    V = tmp

print(max(V) if V else -1)

아이디어 & 풀이

현재 곡에서 연주할 수 있는 음량의 리스트 (e.g., V)을 생성한 뒤 입력받은 ’바꿀 수 있는 볼륨 리스트 D’의 음량 변화량을 순회하면서 업데이트한다.

  • 현재 V 리스트의 원소들에 변화량을 계산한 것 중 범위 내의 볼륨 값만 V으로 추가한다.
    • 계산은 변화량을 더하거나 빼면 된다.
  • V에 직접 추가하면 순회가 계속 돌기 때문에 tmp를 만들어서 추가한 뒤 V를 tmp로 업데이트시킨다.
    • 중복 방지를 위해 집합 자료형을 사용한다.

디버그

  • 처음에 초깃값 입력을 안 했다.
    • V를 [S]로 초기화해서 해결했다.

피드백

tmp 없이 코드를 더 간결하게 작성할 수 있다.

2022.04.05 (JS)

메모리 시간 코드 길이
11380 KB 192 ms 669 B
단계 시작 시각 끝난 시각 걸린 시간
문제 이해 03:06:32 03:08:17
풀이 생각 03:08:18 03:10:32
코딩 03:10:34 03:21:49
디버깅 03:21:50 03:32:05 
const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const [N, S, M] = input[0].split(" ").map((n) => parseInt(n));
const V = input[1].split(" ").map((n) => parseInt(n));

function main() {
    let now = new Set([S]);

    V.forEach((val) => {
        const newVol = new Set([]);
        for (const vol of now) {
            const add = vol + val;
            const sub = vol - val;
            if (0 <= add && add <= M) newVol.add(add);
            if (0 <= sub && sub <= M) newVol.add(sub);
        }
        now = newVol;
    });

    if (!now.size) return -1;
    else return Math.max(...now);
}
console.log(main());

디버그

  • 중복 제거를 안 하고 했더니 메모리 초과가 났다. Set으로 바꿔서 해결했다.

참고 답안

# 풀이 1-1
_, S, M = map(int, input().split())
D, V = [*map(int, input().split())], [S]

for diff in D:
    # 변화량을 더한 결과 리스트와 변화량을 뺀 결과 리스트를
    # 리스트 덧셈 연산으로 합친 뒤
    # set을 한 번 거쳐 중복을 제거한다.
    V = [*set([v + diff for v in V if v + diff <= M] + [v - diff for v in V if v - diff >= 0])]

print(max(V) if V else -1)

# 풀이 1-2
_, S, M = map(int, input().split())
D, V = [*map(int, input().split())], {S}

for diff in D:
    # "res" for v in V    : V 안의 v에서
    #       for res in [v - diff, v + diff] : v로 계산한 리스트 안의 res인 "res"
    # v에 따라 생성된 v - diff, v + diff 결괏값들을 set으로 중복 없이 합친다.
    V = {res for v in V for res in [v - diff, v + diff] if 0 <= res <= M}

print(max(V) if V else -1)

# 풀이 1-3
_, S, M = map(int, input().split())
V = {S}

for diff in map(int, input().split()):
    # 변화량을 더한 결과 집합과 변화량을 뺀 결과 집합을
    # 합집합 연산으로 중복없이 합친다.
    V = {v + diff for v in V if v + diff <= M} | {
        v - diff for v in V if 0 <= v - diff
    }

print(max(V) if V else -1)