#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에서는 한노드를 아에 끝내버리고 가는 느낌을 받았다.

#include <iostream>
using namespace std;

#define MAX_PRICE 1000

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int N, M; cin >> N >> M;
	int P = MAX_PRICE, I = MAX_PRICE;

	int p, i;
	while (M--)
	{
		cin >> p >> i;
		if (p < P) P = p;
		if (i < I) I = i;
	}

	//낱개가 가성비가 제일 좋으면
	if (I * 6 <= P) cout << I * N;
	//패키지가 더 가성비가 좋으면
	else
	{
		//패키지를 사고 남은 기타줄
		int remainI = I * (N % 6);
		cout << P * (N / 6) + ((P < remainI) ? P : remainI);
	}
	return 0;
}

||사고 과정

브랜드 개수만큼 각 가격이 있지만 사실 사용되는건

패키지에서 가장싼것 한개, 낱개에서 가장싼것 한개 이렇게 사용이 되지 않을까 생각을 해서

정렬하지 않고 문제를 풀 수 있을것 같아 테스트케이스에 대입 해보았는데 다 잘 되길래

정렬 과정을 넘기고 최소 값만 받아 풀었다.

||나아 진것

• 테스트 케이스 다 확인 해 본것

다 확인해서 내가 예상했던 예외가 맞는지 확인하여 더 수월하게 풀었다.

• 크기 고려해본것

최대가격에 최대개수를 곱하여 자료형의 크기도 계산했다. 굿굿

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

int main() {

	ios::sync_with_stdio(0), cin.tie(0);
	long t; cin >> t;
	while (t--) 
	{
		long n; cin >> n;
		//방향 입력 받고
		string s; cin >> s;
		bool left(true), right(true);
		//가능방개수
		long cnt(0);

		//방개수만큼 반복
		for (long p = 0; p < n; p++) 
		{
			//양옆중에 양방향이있으면 가능
			if ((s[(n + p - 1) % n] == '-') || (s[p % n] == '-'))
			{
				++cnt; 
			}

			//한방향으로 모두가능한지 체크
			if (s[p] == '<') { right = false; }
			else if (s[p] == '>') { left = false; }
		}

		//어느 한방향으로 모두가능하면 방개수만큼 가능
		if (left || right) { cnt = n; }
		cout << cnt << endl;
	}
	return 0;
}

||사고 과정

내가 너무너무 어렵게 돌아간 문제다..(결국 다른 테스트케이스에서 틀림ㅋㅋㅋㅋㅋ)

단순 방을 한바퀴 돌면서 한쪽으로 모두 가능한지 확인하는게 핵심이였는데

나는 왼쪽으로 한번 돌고 안되면 오른쪽으로 한번 돌아보고 해서 너무 어렵게 갔었다.

하면서도 '아 이거 너무 돌아가는거 같은데?' 라는 생각이 들었는데 그때 바로 잡았어야했다...

암튼 요약하면 이번에는 원형배열을 한바퀴만 돌면서 가능한 문제를

왼쪽으로 돌아보고, 아니면 오른쪽으로 돌아보면서 풀었기에 망했다..

좀 더 로직을 줄일 수 있는지 충분히 생각하자.

||풀면서 느낀 것

• 안풀리는 문제들은 항상 뭔가 마지막이 아쉽다?

여태 다 큰 그림은 맞았으면서도 무언가 하나를 돌아가서 틀리는 경우가 많은데

너무 빠르게 풀려하지말고 시간이 좀 남으면 정말 충분히 생각을 해봐야겠다.

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
#define HMAX 1005
int h[HMAX];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int T; cin >> T;
	while(T--)
	{
		//1. get input
		int N, X; cin >> N >> X;
		int NN = 2 * N;
		for (int i = 0; i < NN; ++i)
		{
			cin >> h[i];
		}

		//2. sort
		sort(h, h + NN, less<int>());

		//3. calculate
		bool bIsCan = true;
		for (int i = 0; i < N; ++i)
		{
			//3-b. 요구한 최소 차이보다 작으면
			if (h[i + N] - h[i] < X)
			{
				bIsCan = false;
				break;
			}
		}

		cout << (string)(bIsCan? "YES\n" : "NO\n");
	}
	return 0;
}

||사고 과정

영어 번역하는데만 15분이 걸렸다ㅋㅋㅋㅋㅋ ㄷㄷ

쭉 정렬하고 앞줄[i]와 뒷줄[i]를 검사하면서 답을 도출하는 그리디 형식이라고 생각이 들었다.

그래서 앞줄과 뒷줄의 차이가 x이상이어야 하는 조건이라 오름차순으로 쭉 정렬하고

i와 i + n 인덱스를 비교하면  앞줄[i]와 뒷줄[i]를 검사하는게 되어 이렇게 검사를 하고

중간에 끊기 위해 bool추가하고 답을 출력했다.

||사용 기법

• Greedy

||풀면서 느낀 것

• 영어 해석을 좀 더 빨리 해봐야겠다.

시간이 걸리더라도 이번처럼 일단 나 혼자 해석해보고 하는게 중요한것 같다.

• 이상,이하,초과,미만

영어에서 이런 범위적인 실수가 조금 나오는데 확실히하고 넘어가야겠다.

||새로 알게 된것

• std::vector end( )

이번에 정확히 알았다.

마지막 원소의 다음번째 주소로 아무것도 가르키지 않는다..!

이걸 왜 사용하냐면 표준 라이브러리의 함수에 범위를 넣으면 마지막 범위는 참조하지 않기 때문에

마지막 원소까지 참조하게 하려고 사용하던 것이였다!

그 예로 sort같은 함수가 있겠다.

sort를 배열로 사용한다면 예시는 이렇다.

int a[5] {1,2,3,4,5};
//마지막 주소인 a + 4의 다음인 a + 5를 end자리에 넣어준다.
sort(a, a + 5);

https://cplusplus.com/reference/algorithm/sort/

https://cplusplus.com/reference/vector/vector/end/