백준 1789번 바로가기

그리디 알고리즘은 지난 포스팅에서 공부했으므로, 다시 설명하지 않는다.

그리디 알고리즘 설명한 문제 바로가기

📌백준 1789번 수들의 합

서로 다른 N개의 자연수의 합 S가 주어지고, N의 최대값을 구하는 문제이다.

어떤 자연수의 합을 이루는 수들이 많으려면, 당연히 작은 수부터 더해 나가야 할 것이다.

for i in range(1, s):
    temp += i
    cnt += 1

작은 수부터 더해서 temp에 저장시키고, 몇번을 더했는지 cnt에 저장했다.

이때, temp가 s와 같아지거나 커지면 반복문을 더 수행할 필요가 없으므로, 조건문을 걸어준다.

if temp >= s:
    break

이제 cnt를 출력해본다.

import sys
input = sys.stdin.readline

s = int(input())

temp = 0
cnt = 0
for i in range(1, s):
    temp += i
    cnt += 1
    if temp >= s:
        break
print(cnt)

문제가 발생한다.

만약 temp가 s와 정확히 같으면 문제가 없겠지만, temp가 증가하다가 s보다 커질 수가 있다.

어차피 개수만 구하는 문제라서 넘어가도 별 상관 없다고 생각했는데 s보다 커지게되면 덧셈연산을 한 번 더 해준 셈 되는 것이다.

그래서 출력조건을 추가해줬다.

import sys
input = sys.stdin.readline

s = int(input())

temp = 0
cnt = 0
for i in range(1, s):
    temp += i
    cnt += 1
    if temp >= s:
        break
if temp == s:
	print(cnt)
else:
	print(cnt-1)

또틀렸다. 맞왜틀?

1부터 차례대로 입력해보니 1일때와 2일때 문제가 발생했다.
👉강제로 1일때와 2일때는 1을 출력하도록 해버렸다.

전체코드

import sys
input = sys.stdin.readline

s = int(input())

temp = 0
cnt = 0
for i in range(1, s):
    temp += i
    cnt += 1
    if temp >= s:
        break

if s == 1 or s == 2:
    print(1)
elif temp == s:
    print(cnt)
else:
    print(cnt-1)

---

📌고찰

• 문제는 맞았지만 제대로 된 로직으로 정확하게 구현한건지 의문이든다.
• 틀렸을때 1이나 0, 혹은 범위의 최대값이 반례인 경우가 많아서 우선적으로 테스트해보는것이 좋다.