문제 링크

이 문제는 탐욕법이 적용되어 최선의 경우만 골라야한다고 생각했다. 일단 규칙성을 파악했을 때, 1+(주어진 값-1), 1+2+(주어진 값 - 1+2), 1+2+3+(주어진 값 - 1+2+3) 이런식으로 최고 많은 조합을 만들어 나갈 수 있었다.

그런데 어느 시점에서 멈춰야할지를 알고 정해야하는데, 주어진 값에 앞선 수들을 뺐을 때, 마지막으로 더한 수보다 남은 수가 작거나 같을 때, 더 이상 더해서 만들 수 없다고 보았다.

처음에 남은 수가 작을 때만 고려해서 97%에서 계속 틀렸다고 나왔는데 조건을 다시 확인해서 정답을 얻어냈다. 계속해서 반례를 찾다가 20일 때 1+2+3+4+5+5=20 이 성립되지 않아야 되는데 카운터 되는 것을 보고 수정할 수 있었다.

감도 못잡으면 아쉬움이 안 남는데, 반례를 못찾아서 틀리는 경우에는 정말 당황스럽고 반례가 쉽게 안 보이는 것 같다. 수 십분동안 반례를 찾느라 고생해보니까 이러한 루트로 찾으면 될 것 같다.

• 최초값, 최후값 검증
• 입력 조건 확인 (예외처리가 부족할 때가 있다)
• 조건부의 등호, 부등호 점검

이정도 파악하고 못찾으면 더 허접한 실수를 저질렀을 확률이 높은 것 같다.

나의 풀이

S = int(input())
tmp = 0
count=1

if S==1:
  count = 1
elif S==2:
  count = 1
else:
  for i in range(1, S+1):
    tmp += i
    if (S - tmp > i):
      count += 1
    else:
      break

print(count)