[백준] 2240번 자두나무

문제: 2240번: 자두나무

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
//#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t, w;
	cin >> t >> w;
	vector<int> trees(t);
	for (int i = 0; i < t; i++) {
		cin >> trees[i];
	}

	// 이동을ㄹ 짝수번 하면 1번 나무에
	// 이동을 홀수번 하면 2번 나무에..
	vector<vector<int>> table(t+1);
	for (int i = 0; i < t + 1; i++) {
		table[i] = vector<int>(w + 1); // 0~w
	}

	for (int i = 1; i < t + 1; i++) {
		for (int j = 0; j < w + 1; j++) {
			// 현재 자두를 받을 수 있으면 +1 헤주기
			int curTree = (j % 2 == 0) ? 1 : 2; // w 가 짝수면 1번 나무, 홀수면 2번 나무

			// 이동하지 않은 경우
			table[i][j] = table[i - 1][j] + (curTree == trees[i - 1]);

			// 이동한 경우 (j>0 인 경우 가능)
			if (j > 0) {
				table[i][j] = max(table[i][j], table[i - 1][j - 1] + (trees[i - 1] == curTree));
			}
		}
	}
	// 최대값 찾기
	int result = 0;
	for (int i = 0; i < w + 1; i++) {
		result = max(result, table[t][i]);
	}
	cout << result;

	return 0;
}

 

진짜 너무 어려웠다;; 현재 자두가 어느 나무에 위치하고 있는지까지 반영해서 문제를 해결해야 했다;;;

 

처음에는 자두가 어느 나무에 위치하고 있는지 까지 배열에 값으로 저장하려고 했는데 이건 너무 산으로 가는 것 같아서 다른 방법을 생각해본 결과 몇 번 이동했는지를 알면 현재 자두가 어느 나무에 위치했는지도 알 수 있다는 거였다.

 

자두는 항상 1번 나무에서 시작하므로 홀수번 이동했으면 2번 나무에 위치하고, 짝수번 이동했으면 1번 나무에 위치한다. 즉, for 문을 돌릴 때 j 의 값이 홀수면 현재 트리의 번호를 2번으로, 아니라면 1번으로 설정하도록 했다.

 

table 에 저장하는 값은 자두를 움직인 경우와 움직이지 않은 경우 중 더 큰 값이다. 움직인 경우와 움직이지 않은 경우 모두 자두를 얻을 수 있는지 여부에 따라 +1 을 해줘야 한다.

 

일단 이동하지 않은 경우는 table[i-1][j] 에 (curTree == trees[i-1]) 를 더한 값과 같다. (curTree==trees[i-1]) 가 참이라면 1을 반환하므로 이를 더해주면 된다. 

 

이동하지 않은 경우를 미리 저장해놓고, 다음에 이동한 경우의 값을 구한 후 max 를 이용해서 더 큰 값으로 갱신하면 된다.

 

마지막에는 for 문 돌면서 t 시간에서 가장 큰 값을 result 로 갱신해주면 된다.

너무 어려워;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;