BOJ_1568 새

TOC {:toc}

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

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

2021.05.18 (Python)

메모리	시간	코드 길이
28776 KB	92 ms	123 B

단계	시작 시각	끝난 시각
문제 이해	20:56:35	20:57:32
풀이 생각	20:57:34	20:57:51
코딩	20:57:52	21:04:37
디버깅	21:04:38	21:12:17

s = 0
i = 0
c = 0

N = int(input())
while s < N:
    i += 1
    c += 1
    if s + i > N:
        i = 1
    s += i

print(c)

디버그

문제 이해를 잘못했다. 중간에 값이 주어진 수보다 커지면 1로 돌아가는 걸 제대로 이해하지 못했다.

피드백

날아가는 새의 수를 주어진 수에서 ‘빼’ 나가면 s 없이도 종결 조건 확인이 가능하다.

2022.03.22 (JS)

메모리	시간	코드 길이
9332 KB	128 ms	505 B

단계	시작 시각	끝난 시각
문제 이해	14:38:55	14:39:35
풀이 생각	14:39:48	14:40:49
코딩	14:40:50	14:51:15

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

const N = Number(input);

function main(N) {
    let K = 1;
    let bird = N;
    let count = parseInt((-1 + (1 + 8 * N) ** 0.5) / 2);
    bird -= parseInt((count * (count + 1)) / 2);

    while (bird > 0) {
        if (bird >= K) {
            bird -= K;
            K += 1;
        } else {
            bird -= 1;
            K = 2;
        }
        count += 1;
    }

    return count;
}

console.log(main(N));

디버그

코드를 다음처럼 더 깔끔하게 적을 수 있다.

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

let N = Number(input);

function main(N) {
    let K = 1;
    let count = parseInt((-1 + (1 + 8 * N) ** 0.5) / 2);
    N -= parseInt((count * (count + 1)) / 2);

    while (N > 0) {
        if (N < K) K = 1;

        bird -= K;
        K += 1;
        count += 1;

    return count;
    }
}

console.log(main(N));

참고 답안 1

N = int(input())
k = 1
s = 0

while N != 0:
    if N < k:
        k = 1
    N -= k
    k += 1
    s += 1
print(s)

참고 답안 2

N = int(input())
s = 0
while N > 0:
    # k를 구한다.
    k = int(((1 + 8 * N) ** 0.5 - 1)) // 2
    s += k
    N -= k * (k + 1) // 2
print(s)

아이디어 & 풀이

다음과 같은 과정을 N이 양수일 동안 반복한다.

1부터 자신까지의 합이 처음 입력받은 수를 ‘넘지 않는 최댓값’ k를 구한 뒤
- 이 과정에서 등차수열의 합 공식을 이용한다.
- 등차수열의 합 공식과 관련해서는 [[boj-1789]]{1789번} 문제의 참고 답안을 참고하면 된다.
이를 출력할 답인 s에 더하고
1부터 k까지의 합을 N에서 뺀다.

해당 과정을 한번 끝내면 다음과 같은 상태가 된다.

남은 새의 수 N이 다음 불러야 하는 수 k + 1보다 작아진다.
문제의 조건대로 k는 1로 초기화되고
이는 동일한 상황에서 새로운 작은 N 값이 주어진 경우와 같다고 볼 수 있다.

그러므로 주어진 수에 다다를 때까지 (N == 0) 같은 과정을 반복하면서 s를 더해 나가면 답을 구할 수 있다.