백준 1789 - 파이썬

https://www.acmicpc.net/problem/1789

1789번: 수들의 합

문제 풀이

이번 문제는 등차수열의 합을 이용해서 풀면 되겠다는 생각이 들었다. 하지만 1부터 20까지 모두 더했을 때 나오는 수는 210이므로 예제 입력 값과 약간 차이가 있었다. 심지어 1부터 20까지는 총 20개인데 예제 출력은 19개가 나왔기 때문에 처음에 더 당황했다. 하지만 문제를 잘 읽어보면 서로 다른 N개의 합이라고만 명시되어 있지 꼭 수가 일정하게 증가해야 한다는 조건은 없다. 그래서 이번에는 반대로 200에서 1씩 증가시키면서 빼보기로 했다.

 

200 - 1 = 199

199 - 2 = 197

198 - 3 = 194

194 - 4 = 190

...

64 - 17 = 47

47 - 18 = 29

29 - 19 = 10

 

10부터는 20을 빼면 음수가 되기 때문에 n의 최댓값은 19가 되는 것이다. 그러면 여기서 드는 의문이 1부터 19까지 다 합해서 200이 되지 않았다는 생각이 들 수 있다. 이는 위에서 말했다시피 꼭 수가 일정하게 증가해야 할 필요는 없기 때문에 19번째 수는 19가 아닌 29가 되면 되는 것이다. 그리고 사실 코드로 구현할 때는 더해진 자연수의 총개수만 구하면 되기 때문에 마지막 수가 19이든 29이든 크게 중요하지 않다. 아래는 위 내용들을 코드로 구현한 것이다.

 

s = int(input())

result = 0
for i in range(1,s+1):
    if s - i < 0:
        break
    print(i,s)
    s -= i
    result = i

print(result)

 

다음 코드는 등차수열의 합 공식을 이용하여 푼 것이다.

s = int(input())

sum = 0
result = 0
n = 0

while True:
    n += 1
    sum = n*(n+1) // 2
    if sum > s:
        break
    result += 1

print(result)

 

이 역시도 200과 정확하게 일치하는지 보다는 n이 몇개인지가 중요하기 때문에 s보다 sum이 클 경우 반복문을 탈출하도록 작성하였다.

 

느낀 점

이번 문제는 처음에 약간 당황하면서 등차수열의 합공식으로 푸는 게 아니면 다른 방법이 뭐가 있나 막막했었는데, 문제에서 주어진 조건들을 잘 활용하고 없는 조건들을 굳이 만들어서 지킬 필요가 없다는 것을 알게 해 준 문제였다. 알고리즘을 풀어나가면서 중요하다고 생각되는 점이 주어진 시간과 입력값의 범위를 잘 확인하여 시간복잡도를 고려한 코드를 작성하는 것이 중요하다는 생각이 있었는데, 주어진 조건을 잘 읽고 그것을 잘 활용하여 푸는 능력 또한 중요하다는 것을 느끼게 되는 문제였다.