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

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

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

	int s;
	int list[9] = { 1,2,3,4,5,6,7,8,9 };
	vector<int> q(9,0);
	stack<int> stc;
	for (int i = 0; i < T; ++i)
	{
		cin >> s;
		for (int j = 9; 0 <= j; --j)
		{
			//원값이 클때
			if (s > j)
			{
				s -= j;
				stc.push(j);
			}
			//같을때
			else if (s == j)
			{
				stc.push(j);
				break;
			}
		}

		while (stc.empty() == false)
		{
			cout << stc.top();
			stc.pop();
		}
		cout << "\n";
	}

	return 0;
}

||사고 과정

먼저 규칙이 있나 확인했다.

input값이 1 ~ 45이기 때문에 분명 규칙이 있을거라고 생각했다.

10은 1 + 9,11은 2 + 9,12는 3 + 9 이런식으로 이루어지는걸 발견하고

뒤에서부터 숫자를 비교해 크면 빼고 작으면 다음, 같으면 종료 하기로 생각했고

또 생각해야할것은 어떻게 출력할까였는데 값을 뒤집어야 했다.

그래서 값을 뒤집기 편한 스택을 사용했다.

||사용 기법

• Greedy
• Stack

||나아 진것

• 규칙을 찾아보는것
• 자료구조를 이용한것

값 뒤집는 스택을 사용한건 편하게 잘 사용한것 같다.