백준 2018 - 수들의 합5

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

2018번: 수들의 합 5

 

 

해당 문제는 단순히 있는 그대로 구현하면, 시간 초과가 나온다.

 

시간 초과가 나온 코드 먼저 보자.

n = int(input())
cnt = 1
s = 0
flag = 0
for i in range(int(n//2)+1, 0, -1):
    s += i
    for j in range(i-1, 0, -1):
        s += j
        flag += 1
        if s == n:
            cnt += 1
            break
        elif s>n:
            break
    if flag == i-1:
        break
    flag = 0
    s = 0

print(cnt)

 

연속된 숫자의 합이 해당 숫자와 같은 가지수를 구하는 문제이므로, 수를 절반으로 쪼개어 반복문을 통해 구해보았다.

결과값은 잘 나오지만, 시간 초과와 메모리 초과로 인해 통과되지 않는다.

이 문제는 시간 초과를 해결하기 위해 반복문이 아닌 투 포인터를 이용하여 구현하는 문제이다.

 

이 문제를 통해 처음으로 투 포인터에 대한 알고리즘을 접했기 때문에, 간단한 설명을 덧붙여 코드리뷰를 해보도록 하겠다.

 

 

 

투 포인터 알고리즘

1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 만들어 활용하는 알고리즘

자세한 풀이는 아래의 포스팅을 참고했다. 굉장히 자세하게 설명되어 있으니 참고할 것

https://konkukcodekat.tistory.com/83

 

이 문제에서는 투 포인트를 활용해서 짧은 시간에 합을 구할 수 있다.

연속된 숫자들의 합은 시작하는 수 + ... + 마지막 수 이므로

합을 s 변수에 저장 후

시작하는 수를 이동시키고, 마지막 수를 이동시켜 그 이동된 수를 빼거나 더하는 식으로 구현하여 굳이 시작하는 수와 마지막 수 사이의 있는 숫자들을 더하는 계산을 할 필요를 없앨 수 있다.

 

풀이코드)

n = int(input())
s, start, end, cnt = 1, 1, 1, 1

while end<n:
    if s<n:
        end += 1
        s += end
    elif s==n:
        cnt += 1
        end += 1
        s += end
    else:
        s -= start
        start += 1
print(cnt)

 

합을 저장하는 변수는 s

시작하는 수가 1이므로 처음 합을 1로 초기화한다.

포인터 2개를 start, end 변수로 두었고 둘다 1로 초기화한다.

가지수를 저장할 변수는 cnt로, 자기자신 그 자체로 한 가지수를 이미 가지고 있으므로 1로 초기화한다.

 

위의 변수들을 활용하여 적용한 알고리즘은 다음과 같다.

 

1. 합이 n이 되어야 하므로 합을 구하는데 사용되는 마지막 수는 n보다 작을 것

=> 그래야 연속된 수의 합이 n이 될 가능성이 있음

(애초에 자기자신은 이미 가지수에 포함됨)

 

2. 합이 n보다 작을 경우 마지막 수를 늘려가며 계속 합을 구함

 

3. 만약, 합이 n과 같다면 가지수를 카운트하고, 마지막 수를 증가시켜 새로운 계산을 시작

 

4. 만약, 합이 n보다 크다면 시작하는 수를 뒤로 이동시킴

=> 마지막 수를 하나씩 증가시키던 중, 합이 n보다 커진 것 이므로 시작하는 수를 증가시키고 원래의 시작한 수를 합에서 빼면 합은 작아질 것이다. 여기에서 또 다른 케이스가 나올 수 있다.

 

n = int(input())
s, start, end, cnt = 1, 1, 1, 1

while end<n:
    if s<n:
        end += 1
        s += end
    elif s==n:
        print(start, end)
        cnt += 1
        end += 1
        s += end
    else:
        s -= start
        s -= end
        end -= 1
        start += 1
print(cnt)

이건 이 글을 쓰면서 다시 풀었던 코드인데, 합이 n보다 작을 때 마지막 수도 같이 줄여줬다.

그랬더니 시간초과 나옴,,

왜 end는 안 줄여줘도 되는 것일까?

어차피 end도 줄여주면 합이 s<n으로 들어가서 end를 다시 1를 증가시키는 연산을 해야하므로 불필요하다.