AtCoder Beginner Contest 175 대회 후기

https://atcoder.jp/contests/abc175

AtCoder Beginner Contest 175 - AtCoder

 

---

 

 

어느덧 8월도 중순이 넘어가고 있습니다. 더운 날씨에 컨디션 조절은 항상 중요합니다. 건강 조심하세요!

A- A번은 늘 생략합니다.

 

B- <In how many ways can we choose three of the sticks with different lengths that can form a triangle?>

1- 다른 길이의 삼각형을 만들기 위해 3개의 스틱을 선택하는 경우의 수는 얼마일까?

2- 삼각형을 만들기 위해 다른 길이의 3개의 스틱을 선택하는 경우의 수는 얼마일까?

해석을 잘못해 1번으로 생각하고 문제를 풀어 시간이 생각보다 오래 걸렸습니다. 2번 해석대로 문제를 풀면 되고

삼각형의 형성 조건은 모두들 아실 거라 생각합니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;

int main()
{
	int N;
	cin >> N;
	vector<ll>v;
    	for(auto&i:v)cin>>i;
	sort(v.begin(), v.end());
    
	int cnt = 0;
	for (int i = 0; i < v.size(); i++)
		for (int j = i + 1; j < v.size(); j++)
			for (int k = j + 1; k < v.size(); k++)
			{
				if (v[i] == v[j] || v[j] == v[k] || v[i] == v[k])continue;
				if (v[i] + v[j]  > v[k]) {
					cnt += 1;
				}
			}
            
	cout << cnt;
}

 

C- 이번 대회의 핵심 문제라고 볼 정도로 얼마나 정확히 빨리 푸느냐가 관건인 문제였습니다.

3개의 변수가 최대 10^15이므로 구현해서 푸는 방법은 당연히 시간 초과가 날것이라 예상할 수 있죠. 그럴 땐 그리디 하게 접근하거나 case를 나눠서 접근하는 방법을 보통 사용합니다. 

case를 나누는 방법도 순탄치만은 않아 보이는데, 한번 접근을 해보면 먼저 X. 초기 점의 좌표를 생각해본다면, case를 어떻게 나눌 수 있을까요? X가 양수일 땐 처음엔 왼쪽으로 움직이고, 음수일 땐 오른쪽으로 움직이고... 그런데 우리가 구하려는 답은 0에 얼마나 가까워져 있는지입니다. 그 말은 좌표를 대칭 이동할 수 있다는 말이죠. 즉, 절댓값을 씌우면 된다는 의미이므로 우리는 -6인 점도 6으로 생각하고, -10110인 점도 10110으로 생각해도 답은 동일하다는 겁니다.

자.. 그럼 이제 K, D변수를 분석해야 할 차례입니다. K는 반복 횟수, D는 이동거리라고 부르죠. 우리는 수직선의 0에 가까워지게 점을 이동시킬 것이며, 점의 좌표는 항상 양수입니다.(*위 문단을 참조) 그렇다면 우리는 처음엔 최대한 왼쪽으로 점을 이동시킬 것입니다. 언제까지요? 점의 좌표가 음수가 될 때까지요. 그러다 아차, 음수가 되었다면 더 이상 왼쪽으로 이동해선 안되니까 다시 오른쪽으로 이동시킵니다. 그다음은? 다시 왼쪽으로 이동. 이 과정이 반복 횟수가 끝날 때까지 반복됩니다. 아. 그럼 우리는 논리적인 식을 세울 수 있겠네요.

1. 점이 최대한 0에 가까이 붙게 이동을 시킨다.
2. 왼쪽으로 1번 이동한다.
3. 오른쪽으로 1번 이동한다. 반복 횟수가 끝나지 않았다면 2번으로 이동.

1번 과정이 끝나기까지 얼마나 점이 이동을 해야할까요? 우리는 몫 연산을 통해 이를 해결할 수 있습니다. 점이 17에있고 이동거리가 3이라면 17/3=5, 5번이면 1번과정이 끝납니다. 또 나머지 연산을 통해 1번과정이 끝난 후의 점의 위치를 알 수도있죠. 17%3=2. 이를통해 1번과정 안에서 반복 횟수가 끝나는 경우의 답을 우리는 도출할 수 있습니다.

 

if (k <= x / d) { cout << x - k*d; }

 

이제 2번과 3번 과정인데, 뭔가 주기가 1이고 반복되니 홀짝 판별 성을 이용해야 할 것 같습니다. 1번 과정이 끝나고 남은 반복 횟수는 K-X/D 임을 알고 있습니다. 쉽게 생각해보죠. 2번 더 이동해야 한다면 왼쪽으로 이동해서 음수가 되었다가 오른쪽으로 이동해서 원위치가 되고. 4번 이동, 6번 이동... 모두 똑같습니다. 반대로 1번 더 이동해야 한다면 왼쪽으로 이동한 다음 끝. 3번 이동, 5번 이동... 모두 똑같습니다. 아, K-X/D가 짝수이면 양수 위치에 있는 점, 홀수면 음수 위치에 있는 점이구나.

 

if ((k - (x/d)) % 2 == 0)cout << x%d;
else cout << abs(x%d - d);

 

이 두 개를 합치면 전체 코드가 됩니다.

 

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

int main()
{
	ll x, k, d;
	cin >> x >> k >> d;
	x = abs(x);
	if (k <= x / d) cout << x - k*d;
	else {
		if ((k - (x / d)) % 2 == 0)cout << x%d;
		else cout << abs(x%d - d);
	}
	
}

 

뭔가 생각한 과정은 길었던 것 같은데 완성 코드는 허무할 만큼 짧습니다. 다른 에지 케이스는 없을까? 하며 의구심이 들면서 제출을 하면 AC가 뜨면서 맞습니다. 여기서 하나의 팁을 드리자면, 이 코드가 맞는지 의구심이 들 때나 제출을 하고 틀려서 반례를 죽어도 못 찾겠다. 할 때 쓰는 유용한 방법이 있습니다. 브루트 포스 설루션을 따로 작성하는 겁니다.

대다수의 문제는 브루트 포스로 치환이 가능합니다. 시간복잡도가 커서 안쓰는건데, 구현은 쉽다는 장점이 있죠. 이를 이용해 봅시다. C번문제의 브루트포스 설루션 함수입니다.

 

ll solution1(ll x, ll k, ll d)
{
	if (k == 0)return abs(x);
	else return min(solution1(x - d, k - 1, d), solution1(x + d, k - 1, d));
}

 

이를 이용해 위에서 작성한 정답 코드를 solution2 함수로 만들고, 반례를 출력해봅시다.

 

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

ll solution1(ll x, ll k, ll d)
{
	if (k == 0)return abs(x);
	else return min(solution1(x - d, k - 1, d), solution1(x + d, k - 1, d));
}

ll solution2(ll x, ll k, ll d)
{
	x = abs(x);
	if (k <= x / d) return x - k*d;
	else {
		if ((k - (x / d)) % 2 == 0)return x%d;
		else return abs(x%d - d);
	}
}
int main()
{
	for (ll i = 1; i <= 10; i++)
		for (ll j = 1; j <= 10; j++)
			for (ll k = 1; k <= 10; k++)
				if (solution1(i, j, k) != solution2(i, j, k)) {
					cout << "wrong answer : " << i << " " << j << " " << k << endl;
					cout << solution1(i, j, k) << "," << solution2(i, j, k) << endl;
				}
}

 

이 방법을 이용하면 자료형 오버플로우 드의 경우를 제외하고는 다양한 반례를 거를 수 있어 유용합니다. 다만, 1분 1초가 중요한 cp에서는 제출 시 간이 늦어지는 만큼 리스크를 안고 가야 하는 점도 있습니다. 하지만 대부분의 cp에서 오답 제출 시 5분 시간 페널티가 있다는 점을 생각해보면 당연 유용할 때도 있겠죠. 브루트 포스 설루션 함수의 구현 시간은 크지 않으니깐 말이죠.

 

D-사이클의 부분 최대합을 찾는 문제인데, 주석으로 설명하겠습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll INF = 987654321987654321;

int main()
{
	int N, K;
	ll ans = -INF;
	cin >> N >> K;
	vector<int>P(N), C(N);
	for (auto&i : P)
	{
		cin >> i;
		i--;
	}
	for (auto&i : C)cin >> i;

	for (int i = 0; i < N; i++)
	{
		int cycleN = 1, now = P[i];
		ll cycleSum = C[i];
		//cycle내의 원소 개수 cycleN과 모든 가치의 합인 cycleSum을 구한다.
		while (now != i)
		{
			cycleN += 1;
			cycleSum += C[now];
			now = P[now];
		}
		//이때까지 경로의 가치 path와 원소의 개수 cnt
		ll path = 0;
		int cnt = 0;
		while (true)
		{
			cnt++;
			path += C[now];
			if (cnt > K)break;
			//cycleN만큼 사이클이 반복되었을때의 점수를 계산
			ll score = path + max((ll)0, cycleSum)*((K - cnt) / cycleN);
			ans = max(ans, score);
			now = P[now];
			if (now == i)break;
		}
	}
	cout << ans;
}

 

E- 한 행에 최대 3개까지만 먹을 수 있을 때, (1,1)에서 (R, C)까지 이동하면서 먹을 수 있는 최대가치의 합을 구하는 문제입니다.

세상에 절대라는 건 없지만, 여러 문제 유형 중에는 몇 가지 법칙이 있습니다. 알고리즘 문제 중에서, (i+1, j)이나(i, j+1)로

예를 들어, https://www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

이 문제는 상하좌우로 이동을 하지만 반드시 대나무가 많은 지역으로 이동을 하므로 중복 방문을 체크할 필요가 없습니다. 즉, DP로 푸는 문제입니다.

https://www.acmicpc.net/problem/1513

1513번: 경로 찾기

역시  (r+1, c) 또는 (r, c+1)로만 이동을 합니다.

혹시 E번의 DP 식을 짜기 어려우신 분은 위의 문제들을 먼저 풀고 접근하시면 훨씬 쉬울 겁니다.

DP라는 접근방법만 알면 이후 코드를 작성하는 법은 어렵지 않습니다. [R위치][C위치][이번 행에서 먹을 수 있는 횟수]의 3차원 배열을 선언하고 재귀 함수를 짜면 됩니다.

 

#include <iostream>
#include <string>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 3000 + 2, INF = 987654321;
int board[MAX_N][MAX_N];
ll cache[MAX_N][MAX_N][4];
int N, M, K;

ll f(int y, int x, int toPick)
{
	if (y == N&&x == M)return (toPick ? board[y][x] : 0);

	ll&ret = cache[y][x][toPick];
	if (ret != -1)return ret;
	ret = 0;

	if (y == N)return ret = (toPick > 0 ? max(f(y, x + 1, toPick - 1) + board[y][x], f(y, x + 1, toPick)) : f(y, x + 1, toPick));
	if (x == M)return ret = (toPick > 0 ? f(y + 1, x, 3) + board[y][x] : f(y + 1, x, 3));

	if (toPick) {
		ret = max(f(y + 1, x, 3) + board[y][x], f(y, x + 1, toPick - 1) + board[y][x]);
	}
	ret = max(ret, max(f(y + 1, x, 3), f(y, x + 1, toPick)));

	return ret;


}

int main()
{
	memset(cache, -1, sizeof(cache));
	memset(board, 0, sizeof(board));
	cin >> N >> M >> K;
	while (K--)
	{
		int r, c, v;
		cin >> r >> c >> v;
		board[r][c] = v;
	}
	cout << f(1, 1, 3);

}