[백준] C++ 주몽(1940)

이 문제는 재료의 고유한 번호의 합을 가지고 갑옷을 만드는 문제이다.

갑옷은 재료를 두 개 사용해서 만든다.

고유한 번호의 합이 M이 되면 갑옷을 만들 수 있다.(만약 M=4이고 고유한 번호가 1, 3)이면 만들 수 있음.

 

문제해결방법

1. 일단 이 문제는 고유한 번호를 입력받으면 정렬을 먼저 해야 한다.

2. 정렬된 데이터를 가지고 앞과 뒤에서 범위를 좁히면서 탐색한다.

 

만약 M으로 9가 들어오면 합이 9가 되는 재료의 조합을 찾으면 된다.

 

1+7=8이고 8은 9보다 작기 때문에 값을 더 키우려면 start를 움직여야 한다. start++

 

start가 한 칸 이동함. 2+7=9이다. M과 값이 같아서 count++를 해준다. 여기서는 start를 ++해줘도 되고 end를 --해줘도 상관없다.

 

이런 식으로 start가 end보다 작을 때까지 탐색을 해주면 된다.(start와 end가 겹치는 부분까지 탐색을 하면 같은 재료를 가지고 갑옷을 만드는 경우가 발생하기 때문에 꼭 start는 end보다 작을 때만 탐색해야 함.)