투 포인터 올바르게 생각하기 기본문제로 연습2

1. 문제

 

2018번: 수들의 합 5 (acmicpc.net)

2018번: 수들의 합 5

 

2. 풀이

 

이전에 풀이한 방식대로, 포인터 i,j를 잡고 구간 [i,j]의 합이 N이 되는지 아닌지를 검사하면 된다

 

자연수 N이 연속된 자연수의 합으로 나타낼려면 결국 N보다 작거나 같은 자연수의 합으로 나타낼 수밖에 없다

 

그러므로 1부터 n까지 natural이라는 배열을 만들었고 (정렬은 왜 한건지 모르겠지만..) 

 

포인터 i,j를 잡은 다음, 초기값 natural[0]로 잡는다

 

이제 [i,j] 구간합이 n보다 작으면, j를 1칸 움직여서 구간합을 증가시킨다.

 

[i,j] 구간합이 n보다 크다면, i를 1칸 움직여서 구간합을 감소시킨다.

 

그리고 [i,j] 구간합이 정확히 n이라면 경우의 수를 1 증가시킨다.

 

그리고 나서가 고민인데.. 

 

i랑 j 포인터 모두 1씩 증가시킨다

 

이동시킬때, 어쨌든구간합을 유지시켜야해서 i를 1 증가시키면 i-1 위치의 원소를 빼주고,

 

j를 1 증가시키면 j 위치의 원소를 더해준다.. 

 

-----------------------------------------------------------------------------------------------------

 

근데 복기하면서 생각해보니까..

 

i,j를 모두 1씩 증가시키거나

 

i만 1 증가시키거나..

 

j만 1 증가시키거나 

 

여기서는 뭘 해도 상관없을듯?

 

어차피 summation > n과 summation < n에서 알아서 포인터 움직이고 summation == n일때 경우의 수를 세주니

 

실제로 뭘 해도 정답!

 

---------------------------------------------------------------------------------------------------------------------------------------

 

from sys import stdin

n = int(stdin.readline())

natural = list(range(1,n+1))

natural.sort()

i = 0
j = 0

summation = natural[0]

answer = 0

while i != n and j != n:
    
    if summation < n:
        
        j += 1

        if j == n:
            
            break

        summation += natural[j]
    
    elif summation == n:

        answer += 1
        i += 1
        j += 1
        summation -= natural[i-1]

        if j == n:
            
            break
            
        summation += natural[j]
    
    else:
        
        i += 1
        summation -= natural[i-1]
    

print(answer)

 

 

아무튼 근데 이러면.. 정답이 아니고 메모리 초과가 뜬다

 

알고보니까 메모리 제한이 32mb더라고

 

문제 의도는 1부터 n까지 배열을 만들지 마라는거지

natural = list(range(1,n+1))

 

근데 이런 경험 많이 해봤지

 

실제로 배열을 만들필요 없이 그냥 포인터를 그대로 summation에 더해주면 그만

 

포인터 i,j를 1로 잡고.. 초기값 summation = 1로 잡은 다음

 

구간합 [i,j]가 n보다 작으면, j를 1 증가시킨다음, j를 그대로 summation에 더해

 

구간합 [i,j]가 n보다 크다면, i를 1 증가시키고./. i-1을 summation에 빼서 구간합 [i,j]를항상 유지시켜

 

구간합 [i,j]가 n과 동일하다면... 경우의 수에 1을 더하고 

 

i,j를 1 증가시키고 summation에 i-1을 뺀 다음, j를 1증가시킨다음 summation에 j를 더해 구간합 [i,j]를 유지 

 

그리고 j가 n+1이 된다면.. 끝이니까 반복문 break

 

from sys import stdin

n = int(stdin.readline())

i = 1
j = 1

summation = 1

answer = 0

while i != n+1 and j != n+1:
    
    if summation < n:
        
        j += 1

        if j == n+1:
            
            break

        summation += j
    
    elif summation == n:

        answer += 1
        i += 1
        j += 1
        summation -= i-1

        if j == n+1:
            
            break

        summation += j
    
    else:
        
        i += 1
        summation -= i-1
    

print(answer)