TIL 23-04-30 백준 알고리즘 - 수들의 합

https://github.com/sdoram/Algorithm

https://github.com/sdoram/algorithm_solving_process

GitHub - sdoram/algorithm_solving_process: 알고리즘 풀이 과정 python 파일

1. 백준 알고리즘 - 수들의 합 

 문제점

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

1789번: 수들의 합

# 서로 다른 N개의 자연수의 합 S

# S가 주어질 때, N의 최댓값 구하기

 시도해 본 것들

입출력 예제 확인하기

answer = 0
for num in range(1, 19+1):
    print(num)
    answer += num
print(answer) # 190

answer = 0
for num in range(2, 20+1):
    print(num)
    answer += num
print(answer) # 209

19개의 숫자를 가지고 200이 안 나와서  문제 이해를 잘못했나 싶어서 문제 확인

문제에서 연속된 숫자라는 조건이 없음을 확인함, 다만 1부터 시작해야 최댓값과 가까워질 테니 기본틀 유지

 

answer = 0
for num in range(1, 19):
    print(num)
    answer += num
print(200 - answer) # 마지막 숫자 = 29
print(answer) # 마지막 전까지 18개 숫자 합 = 171

18개의 숫자까지만 더하고 마지막 숫자는 200에서 남은 값을 모두 할당하면 19개가 되는 것을 확인

 

while문으로 변경하기 

S = 200
count = 1
answer = 0
while S >= answer:
    answer += count
    count += 1

print(count) # 21

숫자의 갯수 겸 더해질 숫자를 나타내는 count를 사용하기 위해 while문 사용 

아직 count가 19가 안됨

 

if문 추가 

if answer + count+1 > S:
    print(count)
    break

누적값 + 다음에 더해질 count 가 S보다 크면이라는 조건 설정

 

S = int(input())
num = 0
count = 1
while True:
    num += count
    if num + count+1 > S:
        print(count)
        break
    count += 1

if문에서 break로 탈출하므로 while문 True로 변경 

제출 시 통과 성공

 

리스트로 더해지는 숫자 확인하기

S = 200
num = 0
num_list = []
count = 1
while True:
    num += count
    num_list.append(count)
    if num + count+1 > S:
        print(count)
        break
    count += 1
print(num_list) #[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

정답은 맞혔지만 더해지는 숫자들을 보고 싶어서 list로 확인할 수 있도록 코드를 추가했다.

리스트로 확인했을 때 숫자의 갯수는 일치하지만 마지막 숫자는 제대로 된 값이 아님을 확인

 

마지막으로 더해지는 숫자 값 구하기 

if num + count+1 > S:
        print(count)
        num_list.pop()
        num_list.append(S-(num-count))

pop()으로 잘못 들어온 마지막 값 제거

S-(num-count)로 200-(190-19) = 29 만들기 

 해결 방법

최댓값 N만 구하는 코드

S = int(input())
num = 0
count = 1
while True:
    num += count
    if num + count+1 > S:
        print(count)
        break
    count += 1

 

리스트로 더해지는 숫자들까지 확인하는 코드 

num = 0
num_list = []
count = 1
while True:
    num += count
    num_list.append(count)
    # S가 200일 때 190 + 19를 하면 초과 하므로 19대신 200을 채웠다는 가정
    if num + count+1 > S:
        print(count)
        # 불가능해지는 숫자 제거
        num_list.pop()
        # 불가능해진 숫자 + 남은 숫자 더한 값 리스트에 추가
        num_list.append(S-(num-count))
        break
    count += 1
print(num_list)
print(sum(num_list))

 알게 된 점

코드 구현 보다 문제를 읽고 이해하는 게 더 어려웠다. 

문제를 그래도 꾸준히 풀고있는데 한 번에 문제를 이해하는 건 어렵다. 이번 문제는 제한 사항이 없는데 스스로 사고를 제한해서 그걸 깨닫는데 시간이 걸렸다.