||문제 이해

각 문제들의 최소 패널티 총합을 구하는 문제

각 문제는 D(풀이 시간), V(오답판정 개수) 가 있다.

풀이 시간 : 시간은 누적된다!

각 문제의 패널티는 D + (20 * V) 로 구해진다.

||해결 계획

처음은 마땅히 좋은 방법이 생각안나서 시간이 작은것 부터 해볼까라는 생각으로 무작정 시작했다.

이 처럼 같은 전략의 반복은 Greedy가 어울려 Greedy를 사용한다.

||계획 검증

두가지 경우가 있다.

시간의 비교, 오답판정의 비교

어떤 경우를 먼저 해야 하는지 검증해본다.

시간의 비교

두개의 문제가 있다 생각한다.

1번 : D = 10, V = 1

2번 : D = 20, V = 1

시간이 작은것부터 할 경우

1. 10 + 20 = 30

2. 30 + 20 = 50

= 30 + 50 = 80

시간이 큰것부터 할 경우

1. 20 + 20 = 40

2. 30 + 20 = 50

= 40 + 50 = 90

즉, 시간은 작은것부터 해야 최소가 나온다.

오답판정의 비교

두개의 문제가 있다 생각한다.

1번 : D = 10, V = 1

2번 : D = 10, V = 2

오답판정이 작은것부터 할 경우

1. 10 + 20 = 30

2. 20 + 40 = 60

= 30 + 60 = 90

오답판정이 큰것부터 할 경우

1. 10 + 40 = 50

2. 20 + 20 = 40

= 50 + 40 = 90

즉, 오답 판정은 상관 없다.

그럼 시간을 오름차순으로 정렬만 해주고 계산해주면 정답이 나온다.

||구현

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

typedef pair<int, int> pii;
#define Time first
#define Verdict second

//시간을 오름차순으로 정렬
bool comp(const pii & a, const pii & b)
{
	return a.Time < b.Time;
}

pii p[MAX];
int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	for (int i = 0; i < MAX; ++i)
	{
		cin >> p[i].Time >> p[i].Verdict;
	}
	sort(p, p + MAX, comp);

	int result = 0;
	int time = 0;
	for (auto data : p)
	{
		time += data.Time;
		result += time + (data.Verdict * 20);
	}

	cout << result;
	return 0;
}

||되돌아 보기

일단 숨겨진 조건을 찾기 어려웠다ㅠ (영어라 내가 해석을 잘 못해서 그런걸 수도 있다...)

그 조건은 시간이 누적된다는 점이다.

처음에는 어 그냥 각 문제마다 D + 20 * V 하면 되는거 아니야? 하고 테스트 케이스를 보고 비교했지만

어림도 없었다.

그러다 생각나게 시험이니까 시간이 누적된 시간으로 계산 하는 것인가? 하고 테스트케이스와 비교해서 알아냈다.

영어도 공부 많이 해야겠다..ㅜ

||문제 이해

무한한 자를 수 없는 테이프를 가지고 구멍을 메꿔라

||해결 계획

물이 새는 위치를 오름차순으로 정렬하고 - O(n log n)

순차적으로 탐색하면서 구멍의 위치와 테이프의 길이를 더하여 그 안에 속한 구멍은 패스한다. - O(n)

= O(n log n + n) = O(n log n)

||계획 검증

1000 * log 1000 이므로 1초내에 충분히 끝날것이다.

||구현

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

int arr[1001];

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

	int n, l; cin >> n >> l;
	for (int i = 0; i < n; ++i)
	{
		cin >> arr[i];
	}
	sort(arr, arr + n);

	int cnt = 0;
	int end = 0;
	for (int i = 0; i < n; ++i)
	{
		end = arr[i] + l;
		++cnt;
		while(arr[i + 1] < end && arr[i + 1] != 0)
		{
			++i;
		}
	}

	cout << cnt;
	return 0;
}

||되돌아 보기

먼저 겹치는 부분은 의미가 없어서 생각에서 제외했고

해결 방법은 테이프는 자를수 없기 때문에 한번 붙일 때 최대한 많은 구멍을 메꾸는 것이다.

이러한 전략을 반복적으로 취해도 문제가 없다면 그리디를 사용하는게 좋을것 같아 그리디를 선택했다.

||개선 코드

#include<cstdio>
int main() {
	bool a[1001] = { 0 };
	int n, l;
	scanf("%d%d", &n,&l);
	while (n--)
	{
		int x;
		scanf("%d", &x);
		a[x] = 1;
	}
	int cnt = 0;
	for (int i = 1; i <= 1000; i++)
	{
		if (a[i])
		{
			cnt++;
			i += l-1;
		}
	}
	printf("%d", cnt);
}

다른 분의 코드이다.

시간 복잡도도 O(N)이며 공간 복잡도도 int형 배열이 아닌 bool형 배열을 사용하여 반으로 낮췄다.

위치를 int배열로 저장하는게 아닌 bool형 배열에 있다 없다로 저장하여 sort연산을 생략하였다!

bool형 배열을 하나의 파이프로 본것이다! 약간 지렸다...

그리고 다음 반복문에서 구멍을 찾는다면 카운팅 후 탐색 인덱스를 테이프 길이만큼 추가해

그 후에 나오는 구멍을 찾게하여 많은 불필요한 연산을 생략했다!

굉장히 배울게 많은 코드였다.

#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

||풀면서 느낀 것

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

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

||나아 진것

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

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

개요

최장증가부분수열에 대해 공부하다가 이분탐색이 필요하게 되어 익히게 됐다.

특징

보통 선형탐색의 경우 O(N)이지만

이진 탐색은 계속 반씩 나누어 나머지 한쪽은 버리는 사이클을 이용하여 탐색을 진행하기 때문에

O(log N)으로 탐색이 가능하다.

단 단점은 정렬된 컨테이너에서만 가능하다.

또한 정확히 반으로 나누지 않을 경우 무한 루프에 빠지는 경우가 있다.

왜 사용하는가?

선형 탐색보다 빠른 속도로 탐색을 진행하려고!

구현

Binary search

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

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

		//중앙 값이 찾는 값인지 확인
		if (arr[m] == f) return m;

		//시작 or 끝 인덱스 조정
		if (arr[m] < f) s = m + 1;
		else e = m - 1;
	}
	return -1;
}

시작 인덱스(s), 중앙 인덱스(m), 끝 인덱스(e) 를 의미하는 정수형 변수로 돌아가게 된다.

m은 항상 (s + e) / 2 로 구할 수 있고

m이 찾는 값보다 크다면 끝 지점을 m으로 옮기고

m이 찾는 값보다 작다면 시작 지점을 m으로 옮긴다.

이렇게 진행하다보면 어느 순간 s와 e가 겹치게 되는데

이때 끝내버리면 m이 s와 e가 겹친 인덱스를 한번도 찾지 못하게 되어서

while ( s < e ) 가 아닌 while ( s <= e ) 를 사용했다.

그 후 교차가 되어서 교차가 되면 끝나고 찾지 못했다는 의미로 -1을 반환하는 형식으로 구현했다.