• TOC {:toc}

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

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

2021.04.28 (Python)

메모리 시간 코드 길이
37352 KB 128 ms 225 B
단계 시작 시각 끝난 시각 걸린 시간
문제 이해 12:07:12 12:07:48
풀이 생각 1 12:12:25 12:13:48
코딩 1 12:13:50 12:20:29
디버깅 1 12:25:15 12:26:53
풀이 생각 2 12:27:06 12:31:10
코딩 2 12:31:13 12:34:45 
from itertools import combinations

N, M = map(int, input().split())
# 주어진 수의 combination을 구해
C = combinations(map(int, input().split()), 3)
# 각 combination의 원소를 더한 리스트를 만들어 정렬한다.
S = sorted(list(sum(c) for c in C), reverse=True)

for s in S:
    # M보다 작거나 같은 s가 나오면
    if s <= M:
        # 출력하고
        print(s)
        # 순회를 끝낸다.
        break

디버그

  • 연속된 세 수를 더한 것보다 그렇지 않은 세 수를 더했을 때 기준에 더 가까울 수 있기 때문에 정렬해서 순차적으로 더하면 안 됐다.

피드백

  • combination을 전부 구한 다음에 최댓값을 찾는 것보다 큰 수부터 완전탐색하다가 조건을 만족했을 때 break 하는 것이 시간이 덜 걸린다.

2022.03.17 (JS)

메모리 시간 코드 길이
15264 KB 184 ms 616 B
단계 시작 시각 끝난 시각 걸린 시간
문제 이해 23:34:48 23:36:08
풀이 생각 11:08:28 11:13:37
코딩 11:13:39 11:36:12 
const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const [N, M] = input[0].split(" ").map((n) => parseInt(n));
const C = input[1]
    .split(" ")
    .map((n) => parseInt(n))
    .sort((a, b) => b - a);

function main(N, M, C) {
    let T = [];

    for (let i = 0; i < N - 2; i++) {
        for (let j = i + 1; j < N - 1; j++) {
            for (let k = j + 1; k < N; k++) {
                const curr = C[i] + C[j] + C[k];
                if (curr === M) return curr;
                else if (curr < M) {
                    T.push(curr);
                }
            }
        }
    }

    return Math.max(...T);
}

console.log(main(N, M, C));

참고 답안

# 풀이 1-1
import sys
input = lambda: sys.stdin.readline().rstrip()

N, M = map(int, input().split())
C = list(reversed(sorted(map(int, input().split()))))

T = set()
# C의 세 수를 완전탐색하면서
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            # 세 수의 합을 s라고 할 때
            s = C[i] + C[j] + C[k]
            # s가 M보다 같거나 작으면
            if s <= M:
                # T에 추가하고
                T.add(s)
                # k의 반복문을 종료한다.
                break

# T의 원소 중 최댓값을 출력한다.
print(max([*T]))

# 풀이 1-2
import sys
input = lambda: sys.stdin.readline().rstrip()

N, M = map(int, input().split())
C = list(reversed(sorted(map(int, input().split()))))

def get_max(N, M, C):
    T = set()
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            for k in range(j + 1, N):
                s = C[i] + C[j] + C[k]
                # 세 수의 합이 M과 같으면
                # 이 값이 최댓값일 수밖에 없기 때문에
                if s == M:
                    # 바로 M을 반환한다.
                    return M
                else:
                    if s < M:
                        T.add(s)
                        break
    return max(T)

print(get_max(N, M, C))

아이디어 & 풀이

M보다 작은 수를 담아두는 변수는 set로 만들면 중복을 자체적으로 걸러준다.

C가 내림차순 되어있어서 ‘현재’의 k를 더한 s가 ‘뒤에 남은’ k 값을 더한 s보다 크기 때문에 처음으로 M보다 작거나 같아지는 s를 찾으면 k의 반복문을 break 한다.

중간에 세 수의 합이 M인지 비교하는 과정을 넣어서 해당 경우 바로 그 값을 반환하도록 할 수도 있다 (풀이 1-2).

  • 중첩된 반복문 안에서 종료가 용이하도록 함수로 정의했다.
  • 함수 안이 아니면 값을 출력한 뒤 sys.exit() 등으로 프로그램을 종료한다.