#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를 핥고 맛을 느낄 줄 알게 된듯하다.

#include <iostream>
using namespace std;

unsigned long long int DP[1001];

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

	//2. Set initial value
	DP[1] = 1;
	DP[2] = 2;

	//3. Set All DP with loop
	for (int i = 3; i <= N; ++i)
	{
		//여기서 mod를 해야 양수에서 mod를 하게 된다.
		DP[i] = (DP[i - 1] + DP[i - 2]) % 10'007;
	}

	//4. Print
	cout << DP[N];
	return 0;
}

||사고 과정

2 x 1일때 부터 2 x 4까지 직접 노가다로 하면서

이전의 타일의 결과 값을 이용할 수 있지 않을까 해서 DP라는 느낌이 강하게 왔다.

그렇게 규칙을 찾긴했는데 뭔가 DP로 푸는 이유가 어정쩡해서 다른 사람들은 왜 DP로 생각했는지 보았는데

이분글이 제일 이해가기 쉬웠다.

명확한 이유 ㄷㄷ

||사용 기법

• DP

||새로 알게 된것

• overflow

이 문제에는 답을 10,007로 나눈 나머지를 출력하라고 나와있어서

나는 Loop을 끝내고 나서 Printf를 했는데 자꾸 오류가 나더라 =~=

알고보니 int형의 overflow때문..

loop때 구해지는 DP의 값이 overflow라면 DP에 들어갈때 DP의 자료형만큼 로 값이 잘리고 다시 더해서 들어가는데

값을 넣기전에 나누고 나머지를 저장하는 식으로 회피했어야 했다.

다시 한번 잘 알게 됐다!

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
using namespace std;

#define MIN(x,y) ((x) < (y) ? x : y)

#define MAX 1001
#define R 0
#define G 1
#define B 2

int DP[MAX][3];
int arr[MAX][3];

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

	int N; cin >> N;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < 3; ++j)
		{
			cin >> arr[i][j];
		}
	}

	//2. Set inital value
	DP[1][R] += MIN(arr[0][G],arr[0][B]) + arr[1][R];
	DP[1][G] += MIN(arr[0][R],arr[0][B]) + arr[1][G];
	DP[1][B] += MIN(arr[0][R],arr[0][G]) + arr[1][B];


	//3. Loop
	for (int i = 2; i < N; ++i)
	{
		DP[i][R] += MIN(DP[i - 1][G],DP[i - 1][B]) + arr[i][R];
		DP[i][G] += MIN(DP[i - 1][R],DP[i - 1][B]) + arr[i][G];
		DP[i][B] += MIN(DP[i - 1][R],DP[i - 1][G]) + arr[i][B];
	}

	//4. Print
	cout << MIN(MIN(DP[N - 1][R],DP[N - 1][G]),DP[N - 1][B]);
	return 0;
}

||사고 과정

약 50분 정도 걸리긴 했지만 나의 힘으로 한번에 풀어서 넘 기쁘당ㅠ

암튼 이번에는 막무가내로 설계하지 않고

테이블을 만들고, 초기 값을 넣고, 점화식을 작성해보려 노력했다.

전에 문제로 생각한 DP란 좀 똑똑한 브루트 포스라고 생각했기 때문에

마지막집이 R일때 ,B일때, G일때 최소값을 다 구하면 될것이라고 생각을 했다.

그렇게 초기 값을 넣는 과정에서 좀 구체적으로 풀이를 파악할 수 있었다.

||사용 기법

• DP1

||풀면서 느낀 것

• 테이블, 초기값, 점화식을 꼭 생각하자

꼭

#include <iostream>
#define MAX 301
using namespace std;
#define Max(x,y) ((x) < (y) ? y : x)

int stairs[MAX];
int DP[MAX];

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

	for (int i = 1; i <= N; ++i)
	{
		cin >> stairs[i];
	}

	//2. Set initial value
	DP[1] = stairs[1];
	DP[2] = stairs[1] + stairs[2];
	DP[3] = Max(stairs[1],stairs[2]) + stairs[3];

	//3. Solve
	for (int i = 0; i <= N; i++)
	{
		DP[i] = Max(DP[i - 2], DP[i - 3] + stairs[i - 1]) + stairs[i];
	}

	//4. Print
	cout << DP[N] << "\n";
}

||사용 기법

• DP

||풀면서 느낀 것

• DP의 응용

이 문제는 여러 형식으로 풀수 있었는데 이걸 통해 여러가지로 사고 방식을 배웠다.

• DP

조금 DP문제를 풀어보면서 약간 똑똑한 브루트 포스 느낌을 받았다.

그래서 이걸 DP로 풀어야하는지 약간 감이 생겼다.

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

int DP[1'000'001];

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

	for (int i = 2; i <= N; ++i)
	{
		//최악의 방법으로 일단 구해놓는다.
		DP[i] = DP[i - 1] + 1;
		if (i % 3 == 0) DP[i] = min(DP[i], DP[i / 3] + 1);
		if (i % 2 == 0) DP[i] = min(DP[i], DP[i / 2] + 1);
	}
	cout << DP[N];
	return 0;
}

||사고 과정

지금 DP를 공부중이라 다른 사람의 코드를 보고 작성한 코드이다.

처음에 혼자 풀때는 규칙을 찾아보면서 이게 왜 DP인지는 알았으나 식을 도출하기가 어려웠다ㅠ

시간제한이 0.15초라 N번만큼 loop를 도는게 아닌거 같았지만 잘 되더라..

암튼 여기서 중요했던건 역시 DP인만큼 이전 값을 활용한다는것!

||사용 기법

• DP

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

#define MAX_MAP 51
#define PUSH(y,x) push(make_pair(y,x))
#define GETY first
#define GETX second

int preX[4] = { 0, 1, 0, -1 };
int preY[4] = { 1, 0, -1, 0 };

int map[MAX_MAP][MAX_MAP];
queue<pair<int,int>> q;
void BFS(const int & Y, const int & X, const int & column,const int & row)
{
	//1. set start node
	q.push(make_pair(Y, X));
	
	//2. loop
	while (q.empty() == false)
	{
		//큐에서 방문 처리
		pair<int, int> temp = q.front(); q.pop();

		if (map[temp.GETY][temp.GETX] == 0) continue;
		map[temp.GETY][temp.GETX] = 0;

		//인접노드 확인
		for (int i = 0; i < 4; ++i)
		{
			int nextX = temp.GETX + preX[i];
			int nextY = temp.GETY + preY[i];
			if (0 <= nextX && nextX < row && 0 <= nextY && nextY < column)
				if (map[nextY][nextX] == 1)
					q.push(make_pair(nextY, nextX));
		}
	}
	return;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int T, M, N, K, X, Y; cin >> T;
	int result;
	while (T--)
	{
		//1. init & get input
		cin >> M >> N >> K;
		result = 0;
		memset(map, 0, sizeof(map));

		while (K--)
		{
			cin >> X >> Y;
			map[Y][X] = 1;
		}

		//2. BFS
		for (int y = 0; y < N; ++y)
		{
			for (int x = 0; x < M; ++x)
			{
				if (map[y][x] == 1)
				{
					BFS(y, x, N, M);
					++result;
				}
			}
		}

		//3. Print
		cout << result << "\n";
	}
	return 0;
}

||사고 과정

단순 그래프로 순회 하면 되는 문제라 특별한건 없지만

내가 한가지 간과해서 틀리게 됐다.

로직의 잘못으로 겹치는 상황인데

방문시에 방문처리를 하고 인접노드를 큐에 넣는게 바로 잘못 된 상황이다.

이런 로직에서는 중복으로 인접 노드를 큐에 넣을 수 있기때문인데

방문처리를 큐에 넣을때 같이 해주어야 이런일이 발생하지 않겠다ㅠ

||사용 기법

• BFS

||풀면서 느낀 것

• BFS에서는 한노드를 아에 끝내버리고 가는 느낌을 받았다.