백준 BOJ 18168 - 라면 사기 (Large)

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

18186번: 라면 사기 (Large)

이 문제는 바로 앞 문제이기도 한

백준 BOJ 18185 - 라면사기 (Small)

이 문제와 크게 다른점이 없다

접근도 동일하고

반례도 동일한데

여기서 신경써야 할점은 딱 하나

저기에서 적어놓은 소스처럼

포문돌리면서 하나씩 빼면 시간초과라서

한번에 빼고 cost에도 한번에 더해줘야 한다.

 

그리고 b <= c인 경우에는 (ex. b를 1로, c를 5로 생각해보자)

세개를 연달아서 사는 경우인 b + 2c가 그냥 한개씩 세번 사는 3b보다 커지게 되므로

여기서 문제가 발생해서 틀리게 된다.

해결법은 그냥 b<c일때 c = b로 설정해주면 깔끔하게 AC가 나온다.

c가 b가 되면, 어차피 b + 2c나 3b나 값이 똑같아지게 되므로,

우리가 원하는 대로 (기존의 그리디로) 처리해도 답이 변하지 않게 된다.

이정도만 작성해주면 깔끔하게 AC.

 

#include <stdio.h>

typedef long long int ll;

ll ramen[1000010] = {0};
ll cost=0;
ll n,b,c;
ll t;

ll min(ll a, ll b){return a>b?b:a;}

void three(ll k){
	ll t = min(ramen[k],min(ramen[k+1], ramen[k+2]));
	ramen[k]-=t;
	ramen[k+1]-=t;
	ramen[k+2]-=t;
	cost+=(b+2*c)*t;
}

void two(ll k){
	ll t = min(ramen[k],ramen[k+1]);
	ramen[k]-=t;
	ramen[k+1]-=t;
	cost+=(b+c)*t;
}

void one(ll k){ cost+=b*ramen[k]; }


int main(){
	scanf("%lld %lld %lld", &n, &b, &c);
	if(b<c) c=b;
	for(int i=0; i<n; i++) scanf("%lld", &ramen[i]);
	for(int i=0; i<n; i++){
		if(ramen[i+1] > ramen[i+2]){
			t = min(ramen[i],ramen[i+1]-ramen[i+2]);
			ramen[i]-=t;
			ramen[i+1]-=t;
			cost+=(b+c)*t;
			
			t = min(ramen[i],min(ramen[i+1], ramen[i+2]));
			ramen[i]-=t;
			ramen[i+1]-=t;
			ramen[i+2]-=t;
			cost+=(b+c+c)*t;
		}
		else{
			t = min(ramen[i],min(ramen[i+1], ramen[i+2]));
			ramen[i]-=t;
			ramen[i+1]-=t;
			ramen[i+2]-=t;
			cost+=(b+c+c)*t;
			
		 	t = min(ramen[i],ramen[i+1]);
			ramen[i]-=t;
			ramen[i+1]-=t;
			cost+=(b+c)*t;
		}
		cost+=b*ramen[i];
		ramen[i] = 0;
	}
	printf("%lld", cost);
	return 0;
}