#include <iostream>
#include <algorithm>

#define MAX 100001
using namespace std;

int dp[MAX][3];
int arr[2][MAX];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	int T; cin >> T;

	while (T--)
	{
		//1. Get input value
		int N; cin >> N;
		for (int i = 0; i < 2; ++i)
		{
			for (int j = 1; j <= N; ++j)
			{
				cin >> arr[i][j];
			}
		}
		
		//2. Set initial value
		dp[1][0] = arr[0][1];
		dp[1][1] = arr[1][1];
		dp[1][2] = 0;

		//3. Do fill DP table
		for (int i = 2; i <= N; ++i)
		{
			dp[i][0] = max(dp[i - 1][2], dp[i - 1][1]) + arr[0][i];
			dp[i][1] = max(dp[i - 1][2], dp[i - 1][0]) + arr[1][i];
			dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]);
		}

		//4. Print
		cout << max(dp[N][0], max(dp[N][1], dp[N][2])) << "\n";
	}
	return 0;
}

||사고 과정

생각하는데 한 40분정도 소모했던 문제였다.

처음에 뭔가 직감적으로 일차원 테이브로는  풀지못하여 이차원 테이블인것 같았지만

인덱스마다 의미하는 것을 찾는게 어려웠다.

DP[ i ] [ j ] 에서 i는 분명 데이터의 개수를 뜻하는 것이니 j의 의미를 찾고 있던 와중에

데이터에서 나올 수 있는 경우의 수를 좀 더 집중적으로 생각했다.

상하좌우로 인접한 스티커는 땔수 없으니

하나의 열(i)에서 위의 스티커를 떼는 경우, 아래의 스티커를 떼는 경우, 떼지 않는 경우를 생각했다.

이 떼지 않는 경우를 생각하기가 어려웠는데 처음 본다고 생각하면

많은 스티커를 떼는게 목표지만 떼지 않는 경우를 구한다 라는게 와닿지 않았던것 때문이였던것 같다.

아무튼 이렇게 세가지를 j에 대응시켜서 손코딩으로 값을 찾아가니 점화식도 나오고 풀게 되었던 문제다.

||사용 기법

• DP

||풀면서 느낀 것

• 이차원 배열 테이블의 느낌

DP[i][j]라면 i는 데이터의 개수이고, j는 데이터에서 나올 수 있는 경우의수 를 뜻하는게 많았던것 같다.

• 넓게 생각하자

처음에는 무조건 많이 떼는게 최대가 나온다고 생각했지만 아니였다.

테스트 케이스가 아니였다면 생각하지 못했을거다.

어떻게 보면 예외처리를 잘하자라는 말ㅋㅋㅠ

• 테이블의 의미를 찾는게 이번에는 도움이 되었다.

경험상 의미를 찾으면 점화식도 금방 나오는것 같기에

다음에는 좀 더 집중해서 찾아봐야겠다.

#include <iostream>
#define MOD 10007
#define ALL 10
using namespace std;
//일차원의 10번째 인덱스는 총합을 의미한다.
long long dp[1001][11] = { 0, };

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;
	for (int i = 0; i < 10; ++i)
	{
		dp[1][i] = 1;
		dp[1][ALL] += dp[1][i];
	}
	
	for (int i = 2; i <= N; ++i)
	{
		dp[i][ALL] = dp[i][0] = (dp[i - 1][ALL]) % MOD;
		for (int j = 1; j < 10; ++j)
		{
			dp[i][j] = (dp[i][j - 1] - dp[i - 1][j - 1] + MOD) % MOD;
			dp[i][ALL] = (dp[i][ALL] + dp[i][j]) % MOD;
		}
	}
	
	cout << dp[N][ALL]<< endl;

	return 0;
}

||사고 과정

처음에 2까지 경우의 수를 작성해보고

0부터 시작하는 경우의수, 1부터 시작하는 경우의 수 이렇게 나누어 생각을 했던것같다.

그렇게 나누어 보다보니까

두자리에서 0으로 시작하는 경우의 수는 한자리의  0 ~ 9로 시작하는 수,

두자리에서 1으로 시작하는 경우의 수는 한자리의  1 ~ 9로 시작하는 수,

...

두자리에서 9으로 시작하는 경우의 수는 한자리의  9로 시작하는 수,

가 나왔다.

그래서 자리수를 i, 시작하는 수를 j로 dp[i][j]형태의 이차원 배열로 테이블을 설정했다.

그 후 점화식을 세워보았고

dp[i][0]은 어쩔 수 없이 dp[i - 1][0] + ...  + dp[i - 1][9] 까지 더해주어야했고

dp[i][1]부터는 dp[i][j] = dp[i][j - 1] - dp[i - 1][j - 1] 이라는 식을 쉽게 세울수 있었다.

||사용 기법

• DP

||풀면서 느낀 것

• 테이블설정 후 점화식 작성

역시 DP는 이렇게 푸니까 많이 수월하다.

||새로 알게 된것

• MOD 관련

코드부터 예외까지 15분정도로 모두 끝냈지만 MOD 연산 때문에 시간이 많이 소요 됐다. 

MOD연산은 오버프로우(음수)를 막기위해 사용되는 것으로 음수가 나와서는 안되는데

중간에 A = ( A - B ) % MOD 이런 연산이 있는데 A - B에서 이미 음수가 나와 MOD를 해도 의미가 없는 경우가 있었다.

그래서 찾은 방법이 MOD를 더해주는것,

A = ( A - B + MOD ) % MOD

||나아 진것

• 깔끔한 풀이 사고 였다.

내가 작성했던 코드

#include <iostream>
#include <string>

using namespace std;

string str;
string f_str;

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	getline(std::cin, str);
	getline(std::cin, f_str);

	int d_length = str.length();
	int f_length = f_str.length();

	int cnt = 0;
	int result;
	while ((result = str.find(f_str)) != string::npos)
	{
		++cnt;
		str = str.substr(result + f_length, d_length);
	}
	cout << cnt;
	return 0;
}

다른 분이 작성한 더 나이스한 방법(하단)

int a;
int main() 
{
	string s, y;
	getline(cin, s); getline(cin, y); 
	auto pos = s.find(y); 
	
	while (pos != string::npos)
	{
		a++;
		pos = s.find(y, pos + y.size());
	}
	cout << a; 
}

||사고 과정

단어 검색이 중복없이 최대로 나오게 하려면 맨앞부터 차근차근 검색해가면 되니까 어려운건 없었고

검색하는 함수를 찾아보는데에 시간이 더 걸렸다.

||풀면서 느낀 것

• 문자열 문제도 항상 하나이상은 풀어야겠다.

문자열 문제는 가끔 풀게 되는데 할때마다 까먹는거 같아서 하루에 한번은 풀어야겠다.

#include <iostream>
#define MOD 9901
using namespace std;

unsigned long long int dp[100'001][2];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	int N; cin >> N;

	dp[1][0] = 1;
	dp[1][1] = 1;

	for (int i = 2; i <= N; ++i)
	{
		dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
		dp[i][0] = (dp[i][1] + dp[i - 1][1]) % MOD;
	}

	cout << ((dp[N][1] * 2) + dp[N][0]) % MOD;
	return 0;
}

||사고 과정

일단 경우의 수를 i가 3일때 까지 그려보았다.

DP로 해결하려 했으니 dp[i - 1]에 추가를 하려고 했던것같다.

그러던 중 추가될 수 있는 마지막이 O X, X O, X X 이렇게 3가지인걸 확인 후

테이블을 2차원 배열로 하려고 생각을 했었다.

이렇게 생각하고 나니까 각 추가될 수 있는 개수가 규칙적으로 나오길래 예외 테스트를 하고 작성하여 풀이했다.

dp[i - 1]에 어떠한 걸 덧 붙일 때 크게 나오는 경우의 수를 찾아서 풀이 하는게 종종 보여서

이런 방법을 잘 기억해두고 있어야겠다.

||사용 기법

• DP

#include <iostream>
#include <algorithm>
using namespace std;

int dp[100'001];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int n; cin >> n;

	dp[1] = 1;	dp[2] = 2;	dp[3] = 3;	dp[4] = 1;

	for (int i = 5; i <= n; ++i)
	{
		dp[i] = i;
		for (int j = 0; j *j <= i; ++j)
		{
			dp[i] = min(dp[i], dp[i - (j * j)] + 1);
		}
	}

	cout << dp[n];
	return 0;
}

||사고 과정

다른 사람의 풀이를 보고서야 해결했던 문제다

나는 처음에 어떠한 규칙이 있을거라고 생각했고 약간 많은 노가다와 억지로 규칙을 이끌었는데

예외가 있었다..

내가 잘못했던건 첫번째로 어떻게 해야 최소 개수를 구할 수 있는지 충분히 생각하지 않았다는 점,

물론 나올 수 있는 최대 제곱수를 이용 하긴 했지만 거기서 더 나아가지 못했다.

두번째로는 예외를 더 생각해보지 않았던 것

이거는 내가 항상 더 많이 주의해야겠다.

||사용 기법

• DP

||풀면서 느낀 것

• 응용

이 문제는 아주 유명한 문제인 최소개수로 동전 거슬러주기 와 비슷한데 동전은 잘 생각했으면서

이건 풀지 못한게 넘 속상하다

• 예외 생각

예외를 생각하기 넘 힘들어서 조금만 해보고 마는 경우가 있는데 앞으로는 일정 시간동안 생각해봐야겠다.

#include <iostream>
#include <queue>

#define MAX 1001
#define X second
#define Y first
using namespace std;

pair<int, int> pre[4] = {{1,0},{0,1},{-1,0},{0,-1}};
int arr[MAX][MAX] = { 0, };
int zeroUnit = 0;

queue<pair<int, int>> q;
int BFS(const int & sizeY, const int & sizeX)
{
	//안익은 토마토가 없으면 바로 0 반환
	if (zeroUnit == 0) return 0;

	int cX, cY, nX, nY;
	int day = 0;
	while (q.empty() == false)
	{
		++day;

		//큐의 길이 만큼(하루 만큼)
		int tempSize = q.size();
		for (int i = 0; i < tempSize; ++i)
		{
			cX = q.front().X;
			cY = q.front().Y;
			q.pop();

			for (int j = 0; j < 4; ++j)
			{
				nX = cX + pre[j].X;
				nY = cY + pre[j].Y;

				//정상적인 범위인지
				if (nY < 0 || sizeY <= nY || nX < 0 || sizeX <= nX) continue;

				//익은 토마토나 장애물이면 패스
				if (arr[nY][nX] != 0) continue;

				//안익은 토마토면 익히고 큐에 삽입
				arr[nY][nX] = 1;
				q.push({ nY,nX });
				--zeroUnit;
			}
		}

		//안익은 토마토 모두 익었으면
		if (zeroUnit == 0) return day;
	}
	return -1;
}

int main()
{
	//1. Get input value
	ios::sync_with_stdio(0), cin.tie(0);
	int x, y; cin >> x >> y;

	for (int i = 0; i < y; ++i)
	{
		for (int j = 0; j < x; ++j)
		{
			cin >> arr[i][j];
			if (arr[i][j] == 1) q.push({i,j});
			if (arr[i][j] == 0) ++zeroUnit;
		}
	}

	//2. Do BFS
	cout << BFS(y, x);
	return 0;
}

||사고 과정

이것도 0을 1로 만드는 최단 반복수를 구하는 BFS였다.

이번에는 BFS다 해 놓고 이차원 배열을 다시 처음부터 끝까지 0이 있나 없나 확인하는 것보다

좀 더 나이스하게 확인 하는 방법이 있는지 더 생각해봤다.

그래서 input을 저장할 때 0의 개수를 저장하고

0을 1로 변경할 때 그 개수를 감소 시켰다.

하루가 지나고 나서 그 개수가 0이 되면 모두 익은것으로 간주하여 return한다.

이러한 방법으로 시간을 좀 많이 줄인것 같아 뿌듯하당

||사용 기법

• BFS

#include <iostream>
#include <queue>
#include <cstring>

#define MAX 301
#define Y first
#define X second
using namespace std;

pair<int, int> pre[8] = {{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2 },{1,-2},{2,-1}};
int arr[MAX][MAX];

int BFS(const int & L,const pair<int, int> & S, const pair<int, int> & E)
{
	//이미 도착일 때
	if (S.X == E.X && S.Y == E.Y) return 0;

	queue<pair<int, int>> q;
	int cX, cY, nX, nY;
	q.push({ S.Y, S.X });

	while (q.empty() == false)
	{
		cY = q.front().Y;
		cX = q.front().X;
		q.pop();

		for (int i = 0; i < 8; ++i)
		{
			nY = cY + pre[i].Y;
			nX = cX + pre[i].X;

			//정상적인 위치인지 확인
			if (nY < 0 || L <= nY || nX < 0 || L <= nX) continue;

			//방문되어있는지 확인
			if (1 <= arr[nY][nX]) continue;

			//도착하면
			if (nY == E.Y && nX == E.X) return arr[cY][cX] + 1;

			//도착이 아니면 큐에 삽입 후 방문처리
			q.push({ nY,nX });
			arr[nY][nX] = arr[cY][cX] + 1;
		}
	}
	return -1;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int T, L; cin >> T;
	pair<int,int> S, E;
	while (T--)
	{
		//set initial value
		memset(arr, 0, sizeof(arr));
		cin >> L;
		cin >> S.Y >> S.X;
		cin >> E.Y >> E.X;

		//Do BFS
		cout << BFS(L, S, E) << "\n";
	}
	return 0;
}

||사고 과정

단순 BFS로 최단 거리를 구하는 문제 특별한 생각이랄건 없었다.

||사용 기법

• BFS

||풀면서 느낀 것

• pair로 이동칸 연산

이번에는 이동칸을 연산하기 위해 배열 두개가 아닌 pair배열로 사용해봤는데 편하고 괜찮았던거 같다.

#include <iostream>
using namespace std;

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;

	string S, T;
	int result;
	int S_one;
	int S_question;
	int T_one;
	for (int k = 1; k <= N; ++k)
	{
		result = 0;
		S_one = 0; S_question = 0;
		T_one = 0;

		//각 일의 개수 구하기
		cin >> S >> T;
		for (int i = 0; i < S.length(); ++i)
		{
			if (S[i] == '1') ++S_one;
			else if (S[i] == '?') ++S_question;
			if (T[i] == '1') ++T_one;
		}

		//변환이 가능한지 확인
		if (T_one < S_one)
		{
			cout << "Case " << k << ": -1\n";
			continue;
		}

		//각 인덱스를 모두 탐색
		for (int i = 0; i < S.length(); ++i)
		{
			//S가 1일때 다른 경우
			if (S[i] == '1' && T[i] == '0')
			{
				//뒤의 0일때 다른 경우의 인덱스와 변경한다.
				for (int j = i; j < S.length(); ++j)
				{
					if (S[j] == '0' && T[j] == '1')
					{
						S[i] = '0'; S[j] = '1'; ++result;
						break;
					}
				}
				//뒤에 0이고 다른 경우가 없으면 T의 1과 맞물리는 물음표와 변경한다.
				if (S[i] == '1')
				{
					for (int j = 0; j < S.length(); ++j)
					{
						if (S[j] == '?' && T[j] == '1')
						{
							S[i] = '0'; S[j] = '1'; result += 2; --S_question;
							break;
						}
					}
				}
			}
			//S가 0일때 다른 경우
			else if (S[i] == '0' && T[i] == '1') 
			{
				//뒤의 1일때 다른 경우의 인덱스와 변경한다.
				for (int j = i; j < S.length(); ++j)
				{
					if (S[j] == '1' && T[j] == '0')
					{
						S[i] = '1'; S[j] = '0'; ++result;
						break;
					}
				}
				//못 찾을 경우
				if (S[i] == '0')
				{
					S[i] = '1'; ++result;
				}
			}
		}

		cout << "Case " << k << ": "<<result + S_question<<"\n";
	}
	return 0;
}

||사고 과정

규칙찾는게 어려웠던 문제다.

문자열 S는 0, 1, ? 로만 이루어져 있으니까 각 숫자에서 T와 다를때

어떻게 해야 중복 없이 최소값이 나올 수 있는지 고민했다.

문자열 S를 한번 싹 탐색하면서 확인한다고 생각했을 때

최대한 물음표가아닌 0, 1을 모두 T와 맞추려고 했다.

이유는 물음표는 어떠한것도 될 수 있기에 0,1만 잘 맞춰놓으면

남은 물음표의 개수만큼 결과에 더하면 되기 때문이다.

S가 1일때 다를 경우:

뒤의 S가 0일때 T와 다른 인덱스와 변경하는게 최고로 좋다고 생각했다.

이유는 뒤의 인덱스까지 맞춰지기 때문.

이러한 경우가 없다면 남은건 뒤의 S가 ?인 인덱스와 변경뿐이다.

S가 0일때 다를 경우: 

이것도 뒤의 S가 1일때 T와 다른 인덱스와 변경하는게 최고로 좋다고 생각했다.

단 이제 이러한 경우가 없을때는 물음표와 변경도 가능하고 0이 1로 변경도 가능하다.

이 둘은 어차피 연산 비용이 2로 같아서 물음표는 나중에 한번에 계산하기도 편하고 해서

0을 1로 바꾸는 계산을 하였다.

이렇게 0,1을 모두 맞추고 남은 물음표의 개수를 결과에 더해주었다.

||사용 기법

• Greedy???

||나아 진것

• 최선을 생각한것 좋았음

경우의 수 중에 어떤 것이 중복없는 최선의 연산인지 확인하는게 좋았다.