[Do-it 코딩 테스트] 007. 주몽의 명령(1940)

문제

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

1940번: 주몽

---

코드

내가 작성한 코드

n = int(input()) # 재료의 개수
m = int(input()) # 갑옷이 완성되는 번호의 합
arr = list(map(int, input().split()))
arr.sort()

start, end = 0, n -1
count = 0
while start < end:
    if arr[start] + arr[end] == m:
        end -= 1
        start += 1
        count += 1
    elif arr[start] + arr[end] > m:
        end -= 1
    else:
        start += 1

print(count)

---

해석

예제 입력	예제 출력
6 # 재료의 개수 9 # 갑옷이 완성되는 번호의 합 2 7 4 1 5 3	2

n = int(input()) # 재료의 개수
m = int(input()) # 갑옷이 완성되는 번호의 합
arr = list(map(int, input().split()))
arr.sort()

start, end = 0, n -1
count = 0

이 문제는 내가 가지고 있는 재료의 개수로 몇개의 갑옷이 완성될 수 있는지를 구하는 문제이며

예를 들어 내가 가지고있는 재료는 6개(2, 7, 4, 1, 5, 3)  갑옷이 완성되는 번호의 합 9라고 했을때

2 + 9, 4 + 5 이렇게 2가지가 있으므로 답은 2이다.

 

여기서 중요한건 한번 쓴 재료는 다시 사용하지 않는다는 점이다.

 

그래서 이 문제에서는 포인터를 뒤로 이동시킬 필요가 없고 한번 쓴 재료를 다시 사용을 하지 못하기 때문에 6번 문제와는 다르게 양족 끝에서 포인터를 각각 시작한다.

 

그래서 start 포인터는 0, end의 포인터값은 n -1이다

0, n-1로 초기화를 해준 이유는 index를 이용할 예정이라 0, n-1로 해주었다.

while start < end:
    if arr[start] + arr[end] == m:
        end -= 1
        start += 1
        count += 1
    elif arr[start] + arr[end] > m:
        end -= 1
    else:
        start += 1

print(count)

몇번을 돌릴지 모르기 때문에 for문 말고 while문을 사용하였고

while문에 조건을 사용해주지 않으면 무한루프에 빠질  수 있어 start < end 엔드 포인터가 start포인터보다 같거나 작을때 반복문을 탈출하게 조건을 걸어주었다.

 

반복문 안에 if문은  이전 6번과 같이 3개인데

 

1. arr[start] + arr[end]의 값과 m이 같을때

arr[start]와 arr[end]의 값을 더한 값과 m이 같을 때에는 end 포인터를 1빼주고 start 포인터를 1증가시켜준 후  count를 1 증가시켜 줘야한다.

 

2.  arr[start] + arr[end] 의 값이 m보다 클때

arr[start]와 arr[end]의 값이 m보다 클 경우에는 end 포인터를 1빼준다 이유는 end 포인터의 숫자가 작아질수록 더한 값은 줄어들기 때문이다.

 

3.  arr[start] + arr[end] 의 값이 m보다 작을때

arr[start]와 arr[end]의 값이 m보다 작을 경우 start 포인터를 1 증가시켜준다 이유는 2번과 마찬가지로 start의 포인터가 커질수록 두개를 더한 값이 커지기 때문이다.

그 후 count를 출력해주면 우리가 얻고싶어했던  연속된 합이 N을 나타내는 수를 구할  수 있다.