#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
#define Strike first
#define Ball second

pii Check(string t, string ask)
{
	int cnt_s = 0;
	int cnt_b = 0;

	for (int i = 0; i < 3; ++i)
	{
		for (int j = 0; j < 3; ++j)
		{
			if (t[i] == ask[j])
			{
				if (i == j) ++cnt_s;
				if (i != j) ++cnt_b;
				break;
			}
		}
	}
	return { cnt_s, cnt_b };
}

string ask[101];
pii sb[101];

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

	for (int i = 0; i < n; ++i)
	{
		cin >> ask[i] >> sb[i].Strike >> sb[i].Ball;
	}

	string temp;
	pii tsb;
	int i, j;
	for (i = 123; i < 988; ++i)
	{
		temp = to_string(i);
		if (temp[0] == temp[1] || temp[0] == temp[2] || temp[1] == temp[2]) continue;
		if (temp[0] == '0' || temp[1] == '0' || temp[2] == '0') continue;

		for (j = 0; j < n; ++j)
		{
			tsb = Check(temp, ask[j]);
			if (sb[j] != tsb) break;
		}
		if (j == n) ++answer;
	}
	cout << answer;
	return 0;
}

||사고 과정

이건 경우의수를 어떻게 for문으로 돌리는지 몰라서 이 부분만 다른 사람의 아이디어를 가져왔다.

내가 너무 어렵게 생각했었다.

123 ~ 987 까지의 순서도 상관없는 모든 경우의수를 어떻게 찾지? 하고 낑낑대며 고민했는데

그냥 123 부터 987까지 1씩 증가하면 되는거였다.....😑

정말 이거 알고 머리가 띵했다.... 바보인듯ㅜ

이 수를 어떻게 돌릴지 알고나서는 수월했다.

각 숫자가 모든 질문에 해당이 되면 카운트를 올린다.

즉 123 ~ 987 까지인 대략 900개와 최대 질문 개수인 100개,

이를 곱한 900 * 100 = 90'000 연산은 1초안에 충분했다.

심지어 가지치기로 122, 131, 424 처럼 중복이 들어간 수는 제외하고

특히 내가 마지막에 못찾았던 0이라는 예외도 처리해주면 더 줄어들것이다.

||사용 기법

• Brute Force

||풀면서 느낀 것

• continue, break

이거 두개를 자꾸 헷갈리게 사용해서 시간을 소모한적이 최근에 많고 이 문제에서도 그랬다.

주의할것

• 문자 비교

바보처럼 자꾸 정수랑 비교한다. 확실히 할것.

char c = '3';

//정수랑 비교 - X		//문자랑 비교 - o
if(c == 3)				if(c == '3')

||새로 알게 된것

• 123 ~ 987

이건 진짜 잘 배운것같다.

지금 아니였으면 또 어딘가에서 헤맸을것.

이 문제처럼 고정 자리인 부분집합에 완전 탐색이면 자주 사용할것 같다.

||다른 풀이

//1.
for(int i = 0; i < n; ++i)
{
	for(int j = 0; j < n; ++j)
	{
		for(int k = 0; k < n; ++k)
		{
			//i가 백의자리숫자, j가 십의자리숫자, k가 일의자리숫자
		}
	}
}


//2.
for(int i = 123; i < 987; ++i)
{
	int a = i / 100;
    int b = i % 100 / 10;
    int c = i % 10;
}

나는 문자로 변환해서 비교했지만

많은 사람들이 이렇게 정수로 비교하곤했다.

#include <bits/stdc++.h>
using namespace std;
#define DP(x) if(dp[x] == 0) dp[x] = x * (x + 1) / 2

int dp[50];

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

	while (t--)
	{
		int n; cin >> n;

		bool pass = false;
		int result_1 = 0, result_2 = 0, result_3 = 0;

		for (int i = 1; i < 50; ++i)
		{
			DP(i);
			result_1 = dp[i];
			if (n < result_1) break;

			for (int j = 1; j < 50; ++j)
			{
				DP(j);
				result_2 = dp[j];
				if (n < result_1 + result_2) break;

				for (int k = 1; k < 50; ++k)
				{
					DP(k);
					result_3 = dp[k];
					if (n < result_1 + result_2 + result_3) break;

					if (result_1 + result_2 + result_3 == n)
					{
						pass = true;
						break;
					}
				}
				if (pass == true) break;
			}
			if (pass == true) break;
		}
		cout << (pass ? "1" : "0") << '\n';
	}
	return 0;
}

||사고 과정

먼저 가장 쉽게 생각 할 수 있는 완전 탐색이 가능한지 생각했다.

3중 for문으로 O(n^3)을 예상하여 n의 최대 값을 대략 구해보려했다.

구하려는 수k는 최대 1000이므로

1000 = n * (n + 1) / 2  → 2000 = n * (n + 1) 이다.

대략적으로 2000 = n^2이라 치면

n이 100일때 k는 10000

n이 50일때 k는 2500

고로 넉넉하게 n을 50이라 생각하면 50^3 = 125,000으로 1초안에 충분히 결과가 나올 수 있을것 같았다.

삼각수는 dp배열에 저장하여 다시 계산하지 않도록 연산을 생략했다.

||사용 기법

• Brute Force
• Dp

||다른 풀이

이건 백트래킹을 이용해 봤다.

#include <bits/stdc++.h>
using namespace std;

#define MAX 50
#define DP(x) if(dp[x] == 0) dp[x] = x * (x + 1) / 2

int dp[MAX];

//total:누적 값, i : 삼각수 번호, len : 재귀의 길이 (one index), n : 찾는 값
bool BT(int total, int i, int len, int n)
{
	if (3 < len) return false;
	
	DP(i);
	total += dp[i];
	if (total == n && len == 3) return true;
	if (n < total) return false;

	for (int k = 1; k < MAX; ++k)
	{
		if(BT(total, k, len + 1, n) == true) return true;
	}

	return false;
}

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

	while (t--)
	{
		int n; cin >> n;
		cout << (BT(0,0,0,n) ? "1" : "0") << '\n';
	}
	return 0;
}

혹은 DP를 다 채우고 하는 사람도 많았다.

#include <bits/stdc++.h>
using namespace std;
#define MAX 50

int dp[MAX];

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

	for (int i = 1; i < MAX; ++i)
	{
		dp[i] = i * (i + 1) / 2;
	}

	while (t--)
	{
		int n; cin >> n;

		bool pass = false;
		for (int i = 1; i < 50; ++i)
		{
			for (int j = 1; j < 50; ++j)
			{
				for (int k = 1; k < 50; ++k)
				{
					if (dp[i] + dp[j] + dp[k] == n) pass = true;
				}
			}
		}

		cout << (pass ? "1" : "0") << '\n';
	}
	return 0;
}

혹은 bool을 만들어서 아에 세가지가 될 수 있는 경우를 모두 저장하여 마지막에 바로바로 출력한다

여러 테스트 케이스가 있다면 이렇게 한번에 채우고 가는게 훨씬 좋은것 같다.

시간복잡도가 훨씬 줄어들었다.

내 생각엔 이 코드가 최고인것 같다.

#include <bits/stdc++.h>
using namespace std;
#define MAX 50

int dp[MAX];
bool b[125000];

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

	for (int i = 1; i < MAX; ++i)
	{
		dp[i] = i * (i + 1) / 2;
	}
	
	for (int i = 1; i < MAX; ++i)
	{
		for (int j = 1; j < MAX; ++j)
		{
			for (int k = 1; k < MAX; ++k)
			{
				b[dp[i] + dp[j] + dp[k]] = true;
			}
		}
	}

	while (t--)
	{
		int n; cin >> n;
		cout << b[n] << '\n';
	}
	return 0;
}

이렇게 필요 없는 코드를 줄여보니까 어떻게 줄여야할지 좀 알았고 담에 좀 더 신경 써야겠다.

#include <iostream>

#define MAX 22
using namespace std;

int N, S;
int arr[MAX];

int result = 0;
void Solve(const int & total, const int & length, int level)
{
	if (1 <= level && total == S)
	{
		++result;
	}

	for (int i = length + 1; i < N; ++i)
	{
		Solve(total + arr[i], i, level + 1);
	}
}

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

	for (int i = 0; i < N; ++i)
	{
		cin >> arr[i];
		if (arr[i] == S) ++result;
	}
	Solve(0, -1, -1);
	cout << result;
	return 0;
}

||사고 과정

처음엔 수열이 N개라면 N^4로 루프를 돌리면서 S에 맞는 값이면 카운트해서 풀이하려고 했다.

근데 쓸모없는 삽질을 통해 중복된 수열이 안된다는 것을 깨달았다..

그래도 이전 문제에서 시간을 줄이려고 하면서 이런 중복된걸 제외하는 코드가 생각나서 좀 쉽게 다가갈 수 있었다.

//중복포함
for(int i = 0; i < N; ++i)
{
	for(int j = 0; j < N; ++j)
	{
		cout << arr[i][j];
	}	
}

//중복제거
for(int i = 0; i < N; ++i)
{
	for(int j = i; j < N; ++j)
	{
		cout << arr[i][j];
	}	
}

이런 느낌인데 이걸 이번 문제에 대입하면

이렇게 볼 수 있다.

각 부모의 숫자보다 이하인 경우는 없다.

이를 이용하여 반복문을 돌려주었고 해결했다.

||사용 기법

• Back tracking

||풀면서 느낀 것

• 문제이해하기

문제만 계속 풀다보니까 집중력이 떨어져서 문제 파악을 잘 못했다.

생각해야할 예외도 많았는데 이 때문에 정말 많은 시간을 소모했다.

• 매개변수의 정확한 의미

length와 level을 두루뭉실하게 잡아놔서 헷갈리는 바람에 시간을 많이 소모함..

항상 단단한 설계가 시간을 아껴준다는걸 느낀다..

||더 나은 풀이

#include <stdio.h>

int a[20];

int n,m;
int cnt =0;

void f(int idx,int sum){
	if(sum==m) cnt++;
	for(int i=idx+1;i<n;i++) f(i,sum+a[i]);
}

int main(void){
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	for(int i=0;i<n;i++) f(i,a[i]);
	printf("%d",cnt);
}

다른 분의 풀이인데 같은 방식이나 내 코드보다 훨씬 많이 최적화 됐다..

나도 풀이할 때 저렇게 for로 재귀를 돌려야하나 싶었는데

나는 메인에 한번만 호출해야한는 고정관념에 갇히고말았다..

담에는 더 분발해야겠다!

그리고 자기 부모인덱스보다 높은 인덱스만을 재귀로 진행했다면 

또 다른 코드는 각 인덱스를 더할지, 말지 로 재귀를 진행하는 코드도 있었다.

#include <iostream>

#define MAX 50
using namespace std;

int N;
int result = 0;
//b는 인덱스는 각 열의 위치를 의미한다.
//값은 이 열에 놓였는지를 뜻한다. true면 놓여있는 것
bool b1[MAX];
//값은 대각선'/'의 판별 식은 a + i
bool b2[MAX];
//값은 대각선'\'의 판별 식은 a - i + n //n을 더해주는것은 음수가 나오지 않게 하기 위해
bool b3[MAX];

void Solve(const int  & a)
{
	if (a == N)
	{
		result++;
		return;
	}

	//i가 어느 열위치에 놓이려고 하는지를 뜻함
	for (int i = 0; i < N; ++i)
	{
		if (b1[i] == true || b2[a + i] == true || b3[a - i + N] == true) continue;

		b1[i] = true;
		b2[a + i] = true;
		b3[a - i + N] = true;
		Solve(a + 1);
		b1[i] = false;
		b2[a + i] = false;
		b3[a - i + N] = false;
	}
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N;
	Solve(0);
	cout << result;
	return 0;
}

||사고 과정

연습하고 있는 백트래킹의 문제

처음에는 중복될수 있는게 많지 않을까? ,중복처리 다 할 수 없을거 같은데? 라는 생각으로 포기할뻔했다.

근데 몇가지 케이스를 직접 그리면서 해보니까 맨 위의 행을 반복하면 중복될 수가 없었다.

역시 뭐든 막연하면 한번 직접해봐야한다.. 안 했으면 포기했을뻔 했다.

암튼 그래서 한 행씩 내려오면서 검사를 하는데

여태 두었던 모든 퀸들의 열과 대각선을 검사해야할까? 해서 한 5까지는 시도해본결과

열은 다 검사하되 대각선은 바로 위의 퀸에만 검사해도 답이 나왔다.

하지만 이건 완전 잘못된 선택..

단지 맵이 작아서 우연히 맞았을 뿐이고 맵이커지면 규칙에 어긋난 배치도 카운팅 됐다.

이렇게 정확히 모를때는 한가지경우라도 범위가 큰 케이스에서 시도를 해보자

결국 한시간이 지나고 다른 사람의 코드를 보았다..

대각선 판별을 깔끔하게 하는걸 보고 놀랐다..

이건 잘 기억해 두어야겠다.

||사용 기법

• Back tracking 

||새로 알게 된것

• 대각선 판별

하나의 대각선' / ' 에 속하는 좌표는 X + Y값이 같다!

그 역 대각선은 X - Y 의 값이 같다!

단 X -Y 는 음수가 나올 수 있기에 배열에 대입하는 경우에는 고정 값을 더해주어야한다

뭔가 알게돼서 넘 좋았다ㅋㅋ

#include <iostream>
using namespace std;
typedef long long int ll;

int pre[16] = { 1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768 };

//0 : 좌측상단 , 1 : 우측상단, 2 : 좌측하단, 3 : 우측하단
int GetQuadrant(const bool & X, const bool & Y)
{
	if (X == true)
	{
		if (Y == true) return 3;
		else return 1;
	}
	else
	{
		if (Y == true) return 2;
		else return 0;
	}
}

ll Func(ll N, ll X, ll Y) 
{
	if (N == 0) return 0;

	//사분면 알아내기
	ll mid = pre[N] / 2;
	ll q = GetQuadrant(mid <= X, mid <= Y);

	//자기사각형에서의 최대값
	ll std = pre[N - 1] * pre[N - 1];
	ll max = std * q;

	//값 합쳐 반환
	return max + Func(N - 1, X % mid, Y % mid);
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	ll N, Y, X; cin >> N >> Y >> X;
	
	cout << Func(N, X, Y);

	return 0;
}

||사고 과정

처음엔 진짜 뭔가 싶었던 1시간 5분 소요해서 풀은 문제...

일단 처음에 함수 형태를 생각했다.

int func(int n, int x, int y)
{
	return "x와 y좌표에 속하는 번호"
}

그리고 규칙을 찾았다.

처음엔 가로 몇번째 줄은 * 2하고  +2를 하고.. 세로는 뭐 어쩌구저쩌구 규칙이 있을까 하면서 생각했다.

그러던 중에 사각형이 4개 뭉텅이로 보이고 각 첫 숫자들이 보이게 됐다.

오 이렇게 16씩 더해지네 하다가 정말 기적처럼 결정적인 아이디어가 생각났다.

속한 사분면에 들어가서 다시 사분면으로 나누고 다시 사분면으로 나누고... 재귀적 아이디어였다.

예를 들어 밑의 별표는 저런식으로 4분면을 쪼개어 들어가는 것이였다.

그렇게 생각하게 된 함수는 이런식으로 변경했다.

int func(int n, int x, int y)
{
	return "2^n * 2^n인 사각형에서 최대로 가질수 있는 수"
}

이걸 생각하고 나서 문제 진행이 수월해졌고

이걸 재귀적으로 다시 수정하면

int func(int n, int x, int y)
{	
	if(n == 0) return 0;
	return "2^n * 2^n인 사각형에서 최대로 가질수 있는 수" + func (n - 1, x, y)
}

이러면 한 변이 2^n인 사각형에서 구할 수 있는 최대 수 + 2^n-1인 사각형에서 구할 수 있는 최대 수 ...

이런식으로 나오기 때문에 답을 구할 수 있겠다고 생각했다.

||사용 기법

• Recursive

||풀면서 느낀 것

• 모르겠을 때는 가만히 있지말고 뭐라도 해라

정말 이것저것 그리거나 규칙을 찾으려고 하지 않았으면 재귀적 아이디어도 떠오르지 않았을 것이다.

||나아 진것

• 재귀적 아이디어를 잘 찾은 것

재귀 문제를 많이 풀어보지 않았는데 혼자 이렇게 생각해 낸것에 대해 약간 뿌듯할지도...😎

#include <iostream>
#include <algorithm>

#define MAX 1'000'002
using namespace std;

pair<int, int> arr[MAX];

bool comp(const pair<int, int> & a, const pair<int, int> & b)
{
	return a.second < b.second;
}

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

	int N; cin >> N;

	for (int i = 0; i < N; ++i)
	{
		cin >> arr[i].first;
		arr[i].second = i;
	}
	sort(arr, arr + N);

	int std = 0;
	for (int i = 0; i < N; ++i)
	{
		//바로 오른쪽이 자신과 같은지 
		if (arr[i].first == arr[i + 1].first) arr[i].first = std;
		else arr[i].first = std++;
	}
	sort(arr, arr + N, comp);
	
	for (int i = 0; i < N; ++i)
	{
		cout << arr[i].first << " ";
	}
		
	return 0;
}

||사고 과정

문제의 Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

는 말이 이해하기 힘들었지만 그냥 최소값부터 압축하라는 뜻..

Upper bound, Lower bound를 공부하면서 보게 된 문제여서 처음에는 Upper bound를 이용해서 풀려고했지만

1, 2, 3, 4, 5 처럼 중복되는 수가 없는 경우면 매 수마다 Upper bound를 하게 되니까 비효율적이라 생각해서

바로 옆에 있는 수를 비교해서 압축하는게 오히려 나을 수도 있겠다고 생각이 들어서 이렇게 풀게 됐다.

||더 나은 풀이

#include <iostream>
#include <algorithm>

#define MAX 1'000'002
using namespace std;

pair<int, int> arr[MAX];
int result[MAX];

bool comp(const pair<int, int> & a, const pair<int, int> & b)
{
	return a.second < b.second;
}


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

	int N; cin >> N;

	for (int i = 0; i < N; ++i)
	{
		cin >> arr[i].first;
		arr[i].second = i;
	}
	sort(arr, arr + N);

	int std = 0; 
	for (int i = 1; i < N; ++i)
	{
		if (arr[i].first != arr[i - 1].first) ++std;
		result[arr[i].second] = std;
	}
	
	for (int i = 0; i < N; ++i)
	{
		cout << result[i]<< " ";
	}
		
	return 0;
}

다른 사람들의 코드를 보던 중에 내 코드에서 sort한번을 생략 할 수 있음을 알았다.

배열을 하나 더 추가해서 arr[i]의 원래 순서의 인덱스에 넣는 방법이였다.

=> result[arr[i[.second] = std;

다른 문제에서 이렇게 원래 순서를 sort해서 가져오는 경우가 종종있었는데 앞으로 좀 더 빠르게 구현할 수 있겠다.

추가로 lower_bound를 이용해 푸는 방법으로 바킹독님 코드를 빌려왔다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int x[1000005];
vector<int> uni; // unique
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x[i];
		uni.push_back(x[i]);
	}
	sort(uni.begin(), uni.end());
	uni.erase(unique(uni.begin(), uni.end()), uni.end());
	for (int i = 0; i < n; i++)
		cout << lower_bound(uni.begin(), uni.end(), x[i]) - uni.begin() << ' ';
}

정렬 후 중복제거를 하게 되면 각 인덱스가 좌표압축한 결과와 같아진다.

ex) 

원본 배열 : [3] [2] [3] [3] [2] [4]

정렬 후 중복제거 : [2] [3] [4]

여기서 [2]는 인덱스가 0으로 2를 좌표압축한 결과와 같고 3, 4 도 마찬가지다.

이분탐색은 인덱스의 위치를 알 수 없으니 lower_bound로 그 위치를  알아내서 풀이하는 방법

#include <iostream>
#include <algorithm>

using namespace std;
int arr[100'002];

int BinarySearch(const int * arr, const int & size, const int & f)
{
	int s = 0, e = size - 1, m;

	while (s <= e)
	{
		m = (s + e) / 2;

		if (arr[m] == f) return 1;
		if (arr[m] < f) s = m + 1;
		else e = m - 1;
	}
	return 0;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	
	int N; cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N);

	int M,F; cin >> M;
	for (int i = 0; i < M; ++i)
	{
		cin >> F;
		cout << BinarySearch(arr, N, F) << "\n";
	}

	return 0;
}

||사고 과정

단순 이분탐색을 사용하는 문제,

직접 구현하여 풀이했다.

||사용 기법

• Binary Search

||더 간단한 풀이

#include <iostream>

using namespace std;
int arr[100'002];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	
	int N; cin >> N;
	int temp;
	for (int i = 0; i < N; ++i)
	{
		cin >> temp;
		arr[temp] = 1;
	}

	int M,F; cin >> M;
	for (int i = 0; i < M; ++i)
	{
		cin >> F;
		cout << (arr[F] == 1 ? 1 : 0) << "\n";
	}

	return 0;
}

이런식으로 정렬 없이 할 수 있을것 같아서 생각해봤지만 들어오는 수의 범위가 int형이므로

int형의 범위만큼 배열을 정의할 수 없기에 비슷한 동작인 Set을 사용해볼것이고

그 중 항상 100% 안정성이 있지는 않지만 빠른 unordered_set을 사용해보았다.

#include <iostream>
#include <unordered_set>

using namespace std;
unordered_set<int> S;

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	
	int N; cin >> N;
	int temp;
	for (int i = 0; i < N; ++i)
	{
		cin >> temp;
		S.insert(temp);
	}

	int M,F; cin >> M;
	for (int i = 0; i < M; ++i)
	{
		cin >> F;
		cout << ((S.find(F) == S.end()) ? 0 : 1) << "\n";
	}

	return 0;
}

여기서 놀라웠던건 시간인데

상수시간을 가지는 u_set보다 n log n의이분탐색이 더 빠르게 나왔다.

O(1)과 O(log N)에서 시간복잡도에 붙은 상수로 자주 뒤집어질수있다고 한다.

항상 상수를 떼고 계산하다보니까 그럴수도 있다는 생각을 하지 못했다.

#include <iostream>
#include <algorithm>

using namespace std;

int dp[10'001][4] = {0,};
int arr[10'001] = {0,};

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

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

	//2. Set initial value
	dp[1][1] = dp[1][0] = 0;
	dp[1][2] = dp[1][3] = arr[1];

	for (int i = 2; i <= n; ++i)
	{
		dp[i][0] = max(dp[i - 1][2], dp[i - 1][3]);
		dp[i][1] = dp[i - 1][0];
		dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + arr[i];
		dp[i][3] = dp[i - 1][2] + arr[i];
	}

	//3. Print
	cout << max(max(dp[n][0], dp[n][1]), max(dp[n][2], dp[n][3]));
	return 0;
}

||사고 과정

비슷한 문제를 좀 풀어서 풀이방법은 어렵지 않게 생각 할 수 있었다.

다만 나는 이차원 테이블을 사용하여 좀 어렵게 풀었다.

이번에도 그냥 감으로 이차원 테이블로 사용했던것 같다.

그래서 dp[ i ][ j ]에서 [ j ]의 경우를 찾으려고 하니까 처음에는 3개가 나왔다.

1번 쉬는 경우, 1번째로 마시는 경우, 2번째로 마시는 경우

사실 2번 쉬는 경우가 포함되어야 하지만 나는 최대로 마실거니까 1번만 쉬어도 되지 않을까 라는 생각을 했다.ㅠ

그래서 처음에 틀렸다가 예외를 찾고 추가하여 정답을 맞췄다.

||사용 기법

• DP

||풀면서 느낀 것

• 테이블을 이차원으로 사용하는 것을 잘 생각해서 설정해야겠다.

요새 이차원으로 DP를 풀다보니 이것도 당연히 이차원일꺼라는 안일한 생각이 있었다ㅠㅠ

감으로 풀지말고 확실한 논리로 테이블을 세팅하자ㅠ

• 이런 문제는 뭔가 어차피 안해도 돼~ 라는 예외가 있는것 같다.

어떠한 경우는 생각해야하지 않을까? 하면 어차피 안해도 되는 예외같은게 많았다.

나는 이 문제에서 i번째 포도주를 안마시고 dp[i - 2]가 최대값일 수도 있지 않나? 라는 생각이 있었는데

필요 없는 예외였다.

다음에는 예외를 좀 더 논리적으로 제거해가야겠다.

||나아 진것

• 예외 생각

다른 사람것을 보지 않고 잘 생각했음

||더 나은 풀이

#include <iostream>
#include <algorithm>

using namespace std;

int dp[10'001] = { 0, };
int arr[10'001] = { 0, };

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

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

	//2. Set initial value
	dp[1] = arr[1];
	dp[2] = arr[2] + arr[1];

	for (int i = 3; i <= n; ++i)
	{
		dp[i] = max(dp[i - 3] + arr[i - 1], dp[i - 2]) + arr[i];
		dp[i] = max(dp[i - 1], dp[i]);
	}

	//3. Print
	cout << dp[n];
	return 0;
}

일차원 테이블로 풀이하는 방법이다.

dp[ i ]는 i번째 포도주에 왔을 때 최대로 마실 수 있는 양을 지닌다.

그 양의 경우의 수는 세가지인데

1) i번째를 두번째로 마시는 경우,

이는 i - 3의 최대 값과 arr[ i - 1 ]을 더해주면 arr[ i ]가 알아서 두번째로 마시는게 된다.

2)i번째를 첫번째로 마시는 경우,

이는 i - 1을 안마신경우이므로 dp[ i - 2 ]에서 현재 arr [ i ]을 더해주면 된다.

3)i번째를 안마시는 경우,

당연히 dp[i - 1] 이다.

dp[i - 2]라는 선택지도 있을것같지만 잘 생각해보면 dp[i - 2] <= dp[i - 1] 가 될 수 밖에 없다.