[SWEA 19113] 식료품 가게 [C/C++]

문제

SW Expert Academy

---

풀이

N개의 할인가와, N개의 원가가 오름차순으로 주어진다.

모든 원가격은 4의 배수이기 때문에 할인가격 또한 정수이다.

 

가격 배열 P에 대해 P(0) 부터 순차적으로 할인가라 가정하자.

P(i)에 대해 P(i + 1) <= P(j) <= P(N) 중 ( P(i) * 4 ) * 3 = P(i)을 만족하는 할인가 P(j)를 찾으면 된다.

이미 탐색한 원가와 할인가는 탐색대상에서 제외( P[i] == -1 )하자.

 

P는 항상 올바르게 주어지기 때문에 위 풀이는 항상 성립한다.

 

할인가는 항상 원가보다 작으며, 오름차순으로 정렬된 P에 대해 순서대로 찾은 할인가들의 배열 res 또한 오름차순 정렬임이 보장된다.

---

문제오류

입력조건이 P(i) <= 109로 되어있다

1 <= P(i) <= 10^9가 올바른 입력조건이다. 때문에 할인가의 원가를 계산할 때 int type이라면, overflow가 발생할 수 있으니 유의하자.

---

소스코드

보기