[Python][SWEA] 7510. 상원이의 연속 합 D3

 

SW Expert Academy

---

🗒️ 파이썬 코드 풀이

T = int(input())
for tc in range(1,T+1) :
    N = int(input())
    cnt = 1
    sum = 0
    i = 2   # 연속이 되기 위한 최소 수
    while True :
        sum += i-1
        if (N-sum) <= 0 :
            break
        if (N-sum) % i == 0:
            cnt += 1

        i += 1
    print(f"#{tc} {cnt}")

 

1. 해당 규칙이 있는데, 이 규칙을 코드로 풀면 된다.

2개 연속  :  n + (n+1) = N   => (N-1) / 2 = n
3개 연속  :  n + (n+1) + (n+2) = N    => (N - (1+2)) / 3 = n
4개 연속  :  n + (n+1) + (n+2) + (n+3) = N   => (N - (1+2+3)) / 4 = n
. . .

k개 연속  :  n + (n+1) + (n+2) + (n+3)  ...  = N   =>  (N - (1+2+3+...k-1)) / k = n

(sum 부분이 N의 크기를 넘는 순간, 연속 불가능 )

🧐 문제 코멘트

참고로 해당 문제은 파이썬으로 제출 할 수 없다. ( 뒤 늦게 알음...)

그래도 한번 포스팅하며 복습하면 좋을 것 같아서 가져와봤다.

N의 범위가 1백만 까지이니 이중 for문은 처다도 보면 안된다. 

최대한 O(N)만 만들로고 간단히 간단히 생각하다가 규칙을 발견했다. 

---

📚 문제

연속적인 것에는 어떤 아름다움이 있다.

상원이는 자연수를 아름답게 쓰는 법을 고민하다가 연속된 자연수의 합으로 표현하기로 했다.

예를 들면, 15는 15 = 7 + 8 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5 로 4가지 방법이 있다.

아름다운 건 다다익선이라고 생각하는 상원이는 표현하고 싶은 자연수 N이 얼마나 많은 경우로 표현될 수 있는 지 궁금해졌다.

상원이를 도와서 문제를 해결하자.


[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 표현하고 싶은 자연수 N(1 ≤ N ≤ 106)이 주어진다.


[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

N을 연속된 자연수의 합으로 표현할 수 있는 경우의 수를 출력하라.