백준 18185 라면 사기 (Small) (c++) : 피너클

18185번: 라면 사기 (Small)

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

 

그리드 문제다. 참 싫다.

 

라면 한개를 사면 3원, 2개를 사면 5원, 3개를 사면 7원이다.

 

이걸 다르게 생각하면

라면 한개를 사면 3원

그 다음에 라면을 사면 2원

그 다음에 또 라면을 사면 2원 이렇게 생각하자.

 

int n;
long long arr[10001];
long long one = 0, two = 0;
long long ans = 0;

사용할 변수들이다.

n이랑 arr은 입력이고 ans는 정답이다.

one은 앞에서 한개를 사면 추가된다.

two는 앞에서 한개를 사고 또 한개를 사면 추가된다.

즉 one -> two로 넘어가는 것이다.

	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];

입력받고

	for (int i = 0; i < n; i++) {
		if (one == 0 && two == 0) {
			ans += 3 * arr[i];
			one += arr[i];
		}

맨 처음부터 전부 확인할것이다.

만약 one도 0이고 two도 0이면 아무것도 안샀거나 0부터 시작하는 그런 상황이다.

정답에 3 * arr[i]을 더해주고 one에는 arr[i]를 더해준다.

우리는 지금 arr[i]개의 라면을 산것이다. 하지만 연속으로 산것은 아니니 당연히 3을 곱해주고

one에다가 지금 산 라면의 개수를 저장해 다음으로 넘어갈때 연속 라면을 사게 해준다.

		else if (one != 0 && two == 0) {
			if (one >= arr[i]) {
				ans += 2 * arr[i];
				
				two += arr[i];
				one = 0;
			}
			else {
				ans += 2 * one;
				ans += 3 * (arr[i] - one);

				two += one;
				one = (arr[i] - one);
			}
		}

만약 one은 0이 아니고 two는 0일때이다.

			if (one >= arr[i]) {
				ans += 2 * arr[i];
				
				two += arr[i];
				one = 0;
			}

one이 arr[i]보다 크거나 같으면, 예를 들어 앞에서 5개의 라면을 샀고 지금 3개의 라면을 사야한다면

ans 에는 2 * arr[i]를 더한다. 앞에서 산 5개의 라면 + 지금 3개의 라면을 산것이다. 이러면 3개의 라면을 연속으로 산게된다.

two에는 arr[i]를 더해준다. 지금 3개의 라면을 산것이니 two += 3이 된다.

one은 0이 된다. 5개의 라면에서 3개의 라면을 연속으로 샀고 이러면 2개의 라면이 남는다. 이것들은 사라진다.

연속으로 가야하니 이번에 연속되지 않은 놈들은 무조건 0으로 없애버린다.

			else {
				ans += 2 * one;
				ans += 3 * (arr[i] - one);

				two += one;
				one = (arr[i] - one);
			}

앞에서 3개의 라면을 샀고 지금 5개의 라면을 사야한다면?

one이 3이고 arr[i]가 5라면

two는 일단 3이 된다. 앞의 3개, 지금의 3개 이렇게 연속으로 가기 때문이다.

그리고 one은 2가 된다. 

앞에서 3개를 샀고 지금 또 연속으로 3개를 샀으니 2개의 라면이 남는다. 이게 one으로 가는 것이다.

one += (arr[i] - one)이 아니다. one = (arr[i] - one) 이다. += 하면 안된다.

		else if (one == 0 && two != 0) {
			if (two >= arr[i]) {
				ans += 2 * arr[i];

				two = 0;
			}
			else {
				ans += 2 * two;
				ans += 3 * (arr[i] - two);

				one += (arr[i] - two);
				two = 0;
			}
		}

one이 0이고 two가 0이 아닐때도 비슷하게 간다.

여기서 two는 무조건 0이 된다.

 

이제 둘다 0이 아니라면 어떻게 해야할까

우리는 3을 더하는 것보다 2를 더하는것이 정답에 더 유리한걸 알고있다.

그러면 우리는 2를 더하는 경우를 더 많이 만들어야 한다.

2를 더하는 경우란 무엇인가?

2를 더하는 경우는 언제인가?

one이 0이 아니거나 two가 0이 아닌 상태이다.

우리는 one부터 하나하나 전부 확인할것이다.

		else {
			long long newtwo = 0;
			if (one >= arr[i]) {
				ans += 2 * arr[i];
				two = arr[i];
				one = 0;
				continue;
			}
			else {
				ans += 2 * one;
				arr[i] -= one;
				newtwo = one;
				one = 0;
			}

one도 0이 아니고 two도 0이 아닌 상태에서

만약 one이 5이고 arr[i]가 3이라면

ans에는 2 * arr[i]을 해준뒤 two를 arr[i]로 바꿔준다.

라면 3개를 연속으로 샀으니 two를 업데이트 해주는 것이다 +=이 아니라 =이다.

그 후 one은 0으로 만들고 뒤에는 continue로 전부 무시한다.

 

만약 one이 3이고 arr[i]가 5라면

ans에는 2 * one을 해주고 arr[i]에 one을 빼준다.

그 후 newtwo를 one으로 해주는데 two를 나중에 업데이트해주려고 하는것이다.

지금 two에다가 one을 더하면 안된다.

one과 two는 지금까지의 것이고 newtwo는 지금의 것이다. 지금의 것은 지금까지의 것을 사용하고 나서 추가시켜준다.

one은 당연히 0으로 해준다. 지금 다 썼기 때문이다.

 

			if (two >= arr[i]) {
				ans += 2 * arr[i];
				one = 0;
				two = newtwo;
				continue;
			}
			else {
				ans += 2 * two;
				arr[i] -= two;
				two = newtwo;
			}

two도 비슷하게 진행된다.

다만 two를 업데이트할때 앞에서 얻은 newtwo를 사용한다.

			ans += 3 * arr[i];
			one = arr[i];
			two = newtwo;
		}
	}

one과 two를 지나고 남은 arr[i]는 무조건 사야하는 하나의 것들이다.

3을 곱해서 더해준뒤 one과 two를 업데이트해준다.

two의 경우 내가 여러번 업데이트를 했는데 그냥 혹시몰라서 한것이다. 원한다면 알아서 빼도 될것이다.

	cout << ans << '\n';

	return 0;
}

그 후 출력하면 끝이다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

int n;
long long arr[10001];
long long one = 0, two = 0;
long long ans = 0;

int main(int argc, char** argv)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];

	for (int i = 0; i < n; i++) {
		if (one == 0 && two == 0) {
			ans += 3 * arr[i];
			one += arr[i];
		}
		else if (one != 0 && two == 0) {
			if (one >= arr[i]) {
				ans += 2 * arr[i];
				
				two += arr[i];
				one = 0;
			}
			else {
				ans += 2 * one;
				ans += 3 * (arr[i] - one);

				two += one;
				one = (arr[i] - one);
			}
		}
		else if (one == 0 && two != 0) {
			if (two >= arr[i]) {
				ans += 2 * arr[i];

				two = 0;
			}
			else {
				ans += 2 * two;
				ans += 3 * (arr[i] - two);

				one += (arr[i] - two);
				two = 0;
			}
		}
		else {
			long long newtwo = 0;
			if (one >= arr[i]) {
				ans += 2 * arr[i];
				two = arr[i];
				one = 0;
				continue;
			}
			else {
				ans += 2 * one;
				arr[i] -= one;
				newtwo = one;
				one = 0;
			}

			if (two >= arr[i]) {
				ans += 2 * arr[i];
				one = 0;
				two = newtwo;
				continue;
			}
			else {
				ans += 2 * two;
				arr[i] -= two;
				two = newtwo;
			}

			ans += 3 * arr[i];
			one = arr[i];
			two = newtwo;
		}
	}

	cout << ans << '\n';

	return 0;
}

전체코드다.