#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???

||나아 진것

• 최선을 생각한것 좋았음

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

#include <iostream>
#include <queue>
using namespace std;
#define MAX 100'000
bool arr[100'001] = { 0, };
int N,K;

queue<pair<int,int>> q;
int BFS(const int & start)
{
	if (N == K) return 0;

	q.push({ start, 0});

	int A, B, C;
	while (q.empty() == false)
	{
		int data = q.front().first;
		int time = q.front().second + 1;

		A = data - 1;	B = data + 1;	C = data * 2;

		if (0 < A && arr[A] == false)
		{
			q.push({ A, time });
			arr[A] = true;
		}
		if (B < MAX && arr[B] == false)
		{
			q.push({B, time });
			arr[B] = true;
		}
		if (C <= MAX && arr[C] == false)
		{
			q.push({C, time });
			arr[C] = true;
		}
	
		if (A == K || B == K || C == K) return time;
		q.pop();
	}

	return -1;
}

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

	return 0;
}

||사고 과정

동적 프로그래밍을 사용하기엔 경우의 수가 너무 많았고

그리디라기엔 바로 나오는게 정답이 아니기에 제외했고

간단한 완전삼진트리??를 탐색하는 그래프로 생각하고 탐색 단계가 곧 시간이기에 BFS를 사용했다.

어찌어찌 N에서 K까지는 갈수 있었지만 처음에 용량 초과로 나와

방문처리용 배열로 중복되는 값들을 제외시켰다.

하지만 이번엔 단계를 구하는 논리가 부족했었다.

그래서 이부분은 다른 사람의 코드를 참고했다ㅠ

제일 나아보였던게 pair로 단계를 저장하여 사용하는것이여서

가져와 정답을 맞추었다.

||사용 기법

• BFS

||풀면서 느낀 것

• 예외 처리

값이 나올 수 있는 예외를 잘 생각하면서 if문을 작성하자

• BFS의 단계 확인

BFS는 아무래도 단계를 구하는게 많다보니 이번에 여러 방법으로 구하는 방법들을 알았다.

pair가 내 기준에서는 가장 깔끔했고, 단계전용 배열을 만들어 사용하는것도 있었다.

||새로 알게 된것

• Pair의 생성

make_pair로만 생성하는줄 알았지만 pair<int, int> a = {1, 2} 이런식으로도 가능!

그래서 이번에 pair의 큐에 push할 때 잘 사용했다.

queue<pair<int,int>> q;
q.push({1,3});

||나아 진것

• BFS 작성 속도

예전보다 빠르게 작성할 수 있게 됐다.

#include <iostream>
#define MOD 1000000000
using namespace std;
long long DP[101][11] = {0,};

int main()
{
	//1. Get input value & Set initial value for DP table
	ios::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;

	for (int i = 0; i <= 9; ++i)
	{
		DP[1][i] = 1;
	}

	//2. Do Loop
	for (int i = 2; i <= 100; ++i)
	{
		DP[i][0] = DP[i - 1][1];
		for (int j = 1; j <= 9; ++j)
		{
			DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j + 1]) % MOD;
		}
	}

	//3. Print
	long long result = 0;
	for (int i = 1; i <= 9; ++i)
	{
		result += DP[N][i];
	}
	cout << result % MOD;
	return 0;
}

||사고 과정

내가 풀지 못한 문제다.

다만 옳은 방법이 생각 났음 에도 아닌거 같아 시도 하지 않았다ㅠ

처음에는 일차원 배열에 각 N마다 나올 수 있는 최대수를 저장한다고 생각했다.

근데 아무리 봐도 이렇게 테이블을 구성하면 안된다고 생각이 들었다.

그래서 i - 1자리에 있는 수를 이용하는 이차원 배열로 테이블을 구성하자고 생각했다.

이게 맞는데 처음에 초기값 세팅을 DP[1][1] = 1; DP[1][2] = 1; ......DP[1][9] = 1; 이렇게 

모두 쓰니까 뭔가 이게 아닌가..?? 느낌이  들어서 삭제했다.....ㅠ

시험 볼때 모두 체크한 답이 모두 4번이면 이상한 느낌이 드는것처럼..

아쉽지만 내가 정확한 점화식을 써놓지 않아서 그렇다고 생각한다!

||사용 기법

• DP

||풀면서 느낀 것

• 점화식 잘 세우기!

정말 몇가지 안되는 예로 점화식 세우는 연습을 많이 해야겠다.

지금 나는 너무 많은 예로 확실히 확인을 하려함

• 이상해도 끝까지 가보기!

#include <iostream>
using namespace std;

int DP[100'0001];

int main()
{
	//1. Get input
	ios::sync_with_stdio(0), cin.tie(0);
	int N, M; cin >> N >> M;
	cin >> DP[1];

	int temp;
	for (int i = 2; i <= N; ++i)
	{
		cin >> temp;
		DP[i] = DP[i - 1] + temp;
	}

	//2. Do loop [ O(N) ]
	int a, b;
	for (int i = 1; i <= M; ++i)
	{
		cin >> a >> b;
		cout << DP[b] - DP[a - 1] << "\n";
	}
	return 0;
}

||사고 과정

아~~ 뭔가 아쉽게 풀이를 하지 못했다.

이미 DP로 푸는 문제인건 알았지만 여러 방식으로 생각하려 했었고

어떠한 숫자들의 합을 미리 구해놓고 이를 이용하는거 까지는 대략 유추했는데

정확한 풀이 까지 가지 못했다.ㅠㅠ

||사용 기법

• DP
• Prefix sum

||풀면서 느낀 것

• DP면 테이블을 확실히 해볼 것

이번 문제는 테이블에 어떤 값을 넣는지만 알면 굉장히 쉽게 풀수 있었다.

다음에 DP로 풀게되면 테이블에 어떤것을 넣을것인가를 중점으로 생각해봐야겠다.

||새로 알게 된것

• Prefix sum

부분합의 알고리즘의 하나인데 이번에 처음 알게 됐다.

0 ~ N 까지  각 i번째에 이전 수들의 합을 모두 저장해놓는다.

그 후 i ~ j 까지의 합을 구하려면

arr[ j ] - arr[ i - 1 ] 로 O(1)에 구해버릴 수 있다.ㄷㄷ

완전 신기함ㅋㅋㅋ

||나아 진것

• 그래도 어느정도 DP를 핥고 맛을 느낄 줄 알게 된듯하다.