백준 18186(라면 사기 Large)풀이

라면 사기 small을 풀고 leinad2님이 large가 small하면 쉽다고 하셔서 풀어봤는데 정말 쉬웠습니다

 

solved.ac 티어 : 다이아 4

www.acmicpc.net/problem/18186

 

이문제를 풀려면 small에서의 조건을 봐야한다

 

1. i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 3원이 든다.

2. i번 공장과 (i+1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-1). 이 경우 비용은 5원이 든다.

3. i번 공장과 (i+1)번 공장, (i+2)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-2). 이 경우 비용은 7원이 든다

 

조건을 보면 1번*2 > 2번이다

만약 1번*2 <= 2번 이면 2개를 살때 2번의 비용보다 1번 2개를 사는 비용이 더 저렴하기 때문이다.

이제 이걸 large에 가지고 와 보자

1. i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 B원이 든다.

2. i번 공장과 (i+1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-1). 이 경우 비용은 (B+C)원이 든다.

3. i번 공장과 (i+1)번 공장, (i+2)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-2). 이 경우 비용은 (B+2C)원이 든다.

 

여기서 B,C가 입력이 주어질때

B*2>(B+C)이라면 라면사기 small 코드를 그대로 사용해주면 된다.

근데 만약 B*2<=(B+C)이라면 라면사기 small코드에서 (B+C)부분(small에서의 5)을 B*2로 바꿔주면 된다.

이제 이걸 그림으로 생각해보자

3개에 7원 1개에 1원인 사과가 있다.

이때 3개를 살때 최소비용으로 살려면 몇개짜리를 사야될까? 바로 1개짜리 3개를 사는게 최소비용이 된다. 이것처럼

그림으로 비교를 했을때 최소비용을 고르면 된다.

 

그리고 코드를 풀이데로 짜고 제출하면.... 틀린다.

여기에 빠진 조건이 하나있다.

만약 B*3<=(B+2C)다 여기서 B*3인 이유는 (B+2C)는 3개고 B는 1개다 그러므로 *3을 해줘서 같은 개수일때를 확인해주는것이다. 이때 B*3이 더 작으면 입력에서의 값들을 모두 더하면 답이된다.

근데 여기서 (B+C)랑 (B+2C)는 구별을 왜 안하는가를 생각할수 있다 하지만 구별을 안하는 이유는

2개로 3개를 만들수 없기 때문이다. 여기서

(B+2*C)+B랑 (B+C)를 비교하면 되지않느냐라고 생각할수있는데 C가 들어있지 않았다면 가능했을것이지만 C가 들어있기때문에 비교할수가 없다 그리고 B랑 (B+2*C)/3의 값이 다른것도 이유이다.

그러므로 2번째와 3번째는 비교하지 않아도 된다.

이제 풀이대로 코드을 짜고 제출하면

 

맞았습니다를 받는다.

 

혼자서 푼 첫 다4들이였네요 ㅎㅎ