백준 2018, 1940, 1253

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

2018번: 수들의 합 5

<내 풀이>

n = int(input())

# 연속된 수의 합이 n을 넘기면 어차피 그 뒤의 값들은 볼 필요가 없어 반으로 나눠줌
end = n // 2 if n % 2 == 0 else n // 2 + 1
A = list(range(1, end + 1))

# 구간합을 구하는 배열을 구함.
S = [A[0]]
for i in range(end-1):
    S.append(S[i] + A[i+1])

# 구간합에 n이 존재한다면 카운트 해줌
count = S.count(n)

target = n
# 구간합의 맨 뒷자리부터 앞에 수들을 하나씩 빼보고
# 뺀 값이 20보다 작아지면 break 후 다음 계산
for i in range(1, len(S) // 2 + 1):
    for j in range(len(S)):
        if S[-i] - S[j] == n:
            count += 1
            break
        if S[-i] - S[j] < n:
            break
            
print(count + 1)

> 정답은 잘 나오지만 메모리 초과가 뜬 코드입니다.... 아무래도 중첩for문 때문일거라고 생각합니다. 우선 수학적 접근 없이 단순히 풀어본 코드로, N을 만들 수 있는 연속된 자연수의 합을 단순히 도출해보았습니다. 

문제집에서는 투포인터를 이용하여 더 간결하게 해답을 도출합니다. 계속해서 인덱스 숫자들을 한칸씩 옮겨보면서 해답을 찾는 방식입니다.

n = int(input())
count = 1
start_index = 1
end_index = 1
sum = 1

while end_index != n:
    if sum == n:
        count +=1
        end_index +=1
        sum += end_index
    elif sum < n:
        end_index +=1
        sum = sum + end_index
    else:
        sum = sum - start_index
        start_index += 1
print(count)

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

1940번: 주몽

<내 풀이>

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
ing=list(map(int,(input().split())))

start_index = 0
end_index = 1
count = 0
while True:
    if ing[start_index]+ing[end_index] == m:
        count += 1

    if end_index < n-1:
        end_index += 1
    elif end_index == n-1:
        start_index += 1
        end_index = start_index + 1
    
    if start_index == n-2:        
        break

print(count)

> n개의 숫자를 받아서 바로 ing라는 list로 만들어주고, 위에 투포인터를 응용하여 숫자를 하나씩 비교했습니다.

우선 두 숫자를 비교해서  m이 되면 카운트 해주고, end_index의 위치에 따라 포인터를 움직여줍니다. end_index가 리스트의 끝에 도달하면 다시 start_index와 end_index를 초기화 해주고 다시 end_index를 움직이며 비교합니다.

만약 start_index가 리스트 맨 마지막의 두번째( 끝에는 end_index가 있으므로)에 도달했다면 비교를 멈췄습니다.

 

정답은 잘 구해지지만 이 역시 시간 초과가 나왔습니다. 해답은 오름차순 정렬입니다. 오름차순 정렬을 함으로써 훨씬 간단하고 짧게 조건문을 만들 수 있었습니다.

 

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
A= list(map(int,(input().split())))
A.sort()

start_index = 0
end_index = n-1
count = 0

# 오름차순을 해줬기 때문에 더한 값을 기준으로 포인터 이동
while start_index < end_index:
    if (A[start_index] + A[end_index]) < m:
        start_index += 1
    elif (A[start_index] + A[end_index]) == m:
        count += 1
        end_index -= 1
        start_index += 1
    else:
        end_index -= 1

print(count)

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

1253번: 좋다

<나의 풀이>

n = int(input())
A = list(map(int,(input().split())))
A.sort()

m = max(A)
i = 0
j = 1
good = 0

# 두 수의 합이 A안에 존재하면 갯수만큼 카운트 해준다.
while i < j:
    good += A.count(A[i]+ A[j])
    
    if A[i]+ A[j] <= m:
        j += 1
    else:
        j -= 1
        i += 1

print(good)

> 비슷한 문제로 좋은 수 찾기 입니다. 오름차순을 통해 두 수의 합이 리스트의 max보다 크다면 포인터를 다시 조정해주고

두 수의 합인 요소가 리스트 안에 있다면 카운트 해주는 방식으로 간단히 완성하였습니다.