슬금슬금 실버 5단계로 올라와서 풀기 시작한 문제다.(아직 수학구현이긴 하지만...)
사실 이 당시의 나한테는 브론즈 2~ 실버 5단계는 나누는 것에 의미가 없었다.
브론즈가 더 어렵게 느껴질 때도 있는 초짜여서 그랬던가^_ㅠ
아무튼 문제의 내용을 요약하자면,
서로 다른 N개의 자연수의 합이 S인데, S가 주어졌을 때 N의 최대 개수를 구하는 것이다.
최소 개수면 그냥 자기 자신을 합한 경우인 1밖에 안 나오기 때문에 최대 개수로 정한 듯하다.
가령, S = 55라면, 우리는 1+2+3+4+5+6+7+8+9+10 = 55 임을 통해 N = 10 임을 알 수있다.
그렇다면 이것을 어떻게 알고리즘으로 나타낼 수 있을지 고민해본다.
우선 S의 값과 숫자를 더했을 때 비교할 변수 ans를 선언한다.
그리고 몇 개의 숫자를 더했는지 체크 할 cnt 변수도 선언한다. 시작은 둘 다 0이다.
무한 루프의 반복문 while 1을 돌린다.
ans에 1부터 시작하는 양의 정수 i의 값이 끊임없이 더해지고,
내부에서 ans가 s보다 크거나 같을 시 break문을 걸기 때문에 반복문이 끝없이 돌 걱정은 없다.
반복문 내에서 끝없이 i가 더해질 경우, 두 가지 경우가 존재한다.
첫째, 차곡차곡 더했을 때 ans의 값이 s와 똑같아지는 경우.
둘째, 차곡차곡 더했을 때 ans의 값이 s를 초과하는 경우.
전자의 경우면 더할나위없이 좋겠지만, 만약 S=54라고 생각해보면 동일한 알고리즘을 적용할때 문제가 발생한다.
1~10까지 더했을 때 55이다. 그러나 우리는 1,2,3..이렇게 차곡차곡 더해왔으므로 9까지 더했을때 45가 된다.
여기서 문제가 발생한다. 더하려면 10을 더해야하고, 빼면 부족하고. 이땐 어떡하지?
조건을 생각해보면 답은 간단하다. 맨 앞에서 더했던 1을 빼면 된다. 그럼 9개의 숫자 2~10을 더해서 54가 된다.
지금 문제에서는 자연수의 '개수'를 구하라고 했지, 그 자연수들을 찾아서 나열하라고 하지 않았다.
그러니 그냥 더한 cnt에서 1을 빼주면 된다.
빼는 자연수가 꼭 1이 아니더라도 가능하다. S=53일 경우, 2라는 자연수를 빼고 1,3,4,5,6,7,8,9,10으로
총 9개의 숫자를 더한 것과 같다.
풀고나서 숏코딩을 구경해보니 아주 단순하게 한 줄의 수학연산식으로 표현한 사람들도 봤는데, 이건 코드를 잘 이해하기가 힘들었다. 따로 찾아봐야 알 것같다.
'공부 > 백준' 카테고리의 다른 글
| [백준] 10103번 (0) | 2022.06.15 |
|---|---|
| [백준] 7568번 (0) | 2022.06.15 |
| [백준] 13305번 (0) | 2022.06.15 |
| [백준] 1764번 (0) | 2022.06.15 |
| [백준] 1205번 (0) | 2022.06.15 |
