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

1.문제설명

두 로봇이 통신하기 위해 이동해야하는 최단 거리를 구해야한다.

두 로봇은 같은 노드에 있거나 서로 연결된 노드에 위치하면 통신할 수 있다.

2.접근방법[알고리즘]

처음에는 문제에 주어진 대로 로봇 두대를 놓고 한 로봇 씩 이동시키면서 

통신할 수 있는지 확인하고 그 때 이동한 거리를 계속 갱신해주면서 답을 구했는데

이러면 n이 10만이기 때문에 시간초과로 틀렸다.

문제의 조건에서

N개의 노드와 N-1의 간선이 있기 때문에

이미 지나온 노드를 재방문 할 수 없을 때

출발 지점에서 도착 지점까지 가는 경로는 무조건 하나만 나오고, 그게 최단 경로가 된다.

이 문제를 해결하려면

1. 두 로봇의 시작점 사이의 거리를 구한다.

2. 시작점을 이어주는 통로 중 길이가 가장 긴 간선을 구한다.

3. 답 = 시작점 사이 거리 - 가장 긴 간선 거리 

3.문제풀이코드 C++

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

int n, s1, s2;
vector<pair<int, int> > m[100001];

bool ch[100001];
bool flag = false;

void DFS(int x, int sum, int max_dist) {
	if (flag) return;
	if (x == s2) {
		cout << sum - max_dist << '\n';
		flag = true;
		return;
	}

	for (int i = 0; i < m[x].size(); i++) {
		int nx = m[x][i].first;
		int nd = m[x][i].second;
		if (ch[nx] == 0) {
			ch[nx] = 1;
			DFS(nx, sum + nd, max(nd,max_dist));
		}
	}

	return;
}

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

	cin >> n >> s1 >> s2;
	for (int i = 0; i < n - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		m[a].push_back({ b,c });
		m[b].push_back({ a,c });
	}
	ch[s1] = 1;
	DFS(s1, 0, 0);

	return 0;
}

DFS를 돌면서 다른 로봇의 시작점을 만나면 바로 종료해주면 된다.

해당 정점까지 가는 다른 방법이 존재하지 않기 때문이다.

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

Segment Tree 공부하기

겉보기에는 구간합을 구하는 간단한 문제처럼보이지만

Segment Tree 자료구조를 이해해야 풀 수 있는 문제입니다.

하단 링크에 설명이 잘 되어 있습니다.

https://www.acmicpc.net/blog/view/9

하단의 영상은 제가 올린 건 아니고

유튜브에 개발자영맨님이 만든 Segment Tree 강의인데

설명이 잘 되어 있어서 같이 올려봅니다.

https://www.youtube.com/watch?v=075fcq7oCC8 

https://www.youtube.com/watch?v=ahFB9eCnI6c 

문제풀이코드 C++

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

int n, m, k;
long long arr[1000003];

struct SegmentTree {
	int N;
	vector<long long> tree;

	long long merge(long long left, long long right) {
		return left + right;
	}

	long long buildRec(int node, int nodeLeft, int nodeRight) {
		if (nodeLeft == nodeRight) {
			return tree[node] = arr[nodeLeft];
		}

		int mid = (nodeLeft + nodeRight) / 2;

		long long LeftVal = buildRec(2 * node, nodeLeft, mid);
		long long RightVal = buildRec(2 * node + 1, mid + 1, nodeRight);

		return tree[node] = merge(LeftVal, RightVal);
	}

	void init(int Size) {
		N = Size;
		tree.resize(N * 4);
		buildRec(1, 0, N - 1);
	}

	long long queryRec(int left, int right, int node, int nodeLeft, int nodeRight) {
		// 노드 구간이 구하는 구간 밖일 경우 0 리턴
		if (nodeRight < left || right < nodeLeft) {
			return 0;
		}

		if (left <= nodeLeft && nodeRight <= right) {
			return tree[node];
		}

		int mid = (nodeLeft + nodeRight) / 2;
		long long leftVal = queryRec(left, right, 2 * node, nodeLeft, mid);
		long long rightVal = queryRec(left, right, 2 * node + 1, mid + 1, nodeRight);

		return merge(leftVal, rightVal);
	}


	long long query(int left, int right) {
		return queryRec(left, right, 1, 0, N - 1);
	}

	long long updateRec(int index, long long newValue, int node, int nodeLeft, int nodeRight) {
		if (nodeRight < index || index < nodeLeft) return tree[node];
		
		if (nodeLeft == nodeRight) {
			return tree[node] = newValue;
		}

		int mid = (nodeLeft + nodeRight) / 2;
		long long leftVal = updateRec(index, newValue, 2 * node, nodeLeft, mid);
		long long rightVal = updateRec(index, newValue, 2 * node + 1, mid + 1, nodeRight);


		return tree[node] = merge(leftVal, rightVal);
	}


	void update(int index, long long newValue) {
		updateRec(index, newValue, 1, 0, N - 1);
	}

};


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

	cin >> n >> m >> k;

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

	SegmentTree st;
	st.init(n);

	for (int i = n + 2; i <= n + m + k + 1; i++) {
		int a, b;
		long long c;
		cin >> a >> b >> c;

		if (a == 2) {
			cout << st.query(b - 1, c - 1) << '\n';
		}
		else {
			st.update(b - 1, c);
		}
	}

	
	return 0;
}

백준 2042 반례

5 1 1
1
2
3
4
5
1 2 300000000000
2 2 5

answer: 300000000012

a, b, c 를 입력 받을 때 c를 long long 형으로 입력받아야합니다.

업데이트를 해주는 과정에서도 long long 자료형을 유지해 업데이트를 진행해야합니다.

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

1.문제설명

INPUT

12ab112ab2ab
12ab

첫 째로 일반 문자열이 주어지고

두번째로 폭발하는 문자열이 주어진다.

1. 일반 문자열 내에 폭발 문자열이 있을 경우 폭발 문자열을 없애줘야한다.

2. 폭발 문자열을 없앤 결과 또 폭발문자열이 포함되어 있을 경우 다시 폭발문자열을 없애줘야한다.

1과 2를 문자열 내에 폭발문자열이 없을 때까지 반복한다.

2.접근방법[알고리즘]

그동안 습관적으로 STL을 사용하던 버릇에 긴장감을 주는 문제다.

스택을 직접 구현해야 가장 편하게 풀 수 있다.

입력받은 첫째 문자열을 돌면서 stack에 char 문자 하나씩 넣어주다가

stack의 가장 위 문자가 폭발 문자열의 마지막 문자와 동일하면

그 문자가 폭발 문자열을 이루고 있는지 확인하고,

폭발문자열이 발견되면 그만큼 pop 해주어야한다.

pop 해주는 건 p 변수를 폭발문자열의 크기 만큼 빼주면 쉽게 구현할 수 있다.

3.문제풀이코드 C++

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

char stack[1000001];
int p = 0;
string str;
string bomb;

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

	cin >> str;
	cin >> bomb;
	
	for (int i = 0; i < str.length(); i++) {
		stack[p++] = str[i];

		if (p >= bomb.length() && stack[p - 1] == bomb[bomb.length() - 1]) {
			bool is_same = true;
			for (int j = 0; j < bomb.length(); j++) {
				if (bomb[j] != stack[p - bomb.length() + j]) {
					is_same = false;
				}
			}
			if (is_same) {
				p -= bomb.length();
			}
		}
	}

	if (p == 0) {
		cout << "FRULA" << '\n';
	}
	else {
		for (int i = 0; i < p; i++) {
			cout << stack[i];
		}
		cout << '\n';
	}


	return 0;
}

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

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

int n, k;
string str;

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

	cin >> n >> k;
	cin >> str;

	deque<char> Q;

	for (int i = 0; i < str.length(); i++) {
		while (k && !Q.empty() && Q.back() < str[i]) {
			Q.pop_back();
			k--;
		}
		Q.push_back(str[i]);
	}

	for (int i = 0; Q.size() - k; i++) {
		cout << Q.front();
		Q.pop_front();
	}

	return 0;
}

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

1.문제설명

......
......
......
......
......
......
......
......
.Y....
.YG...
RRYG..
RRYGG.

12 * 6 으로 Input이 주어질 때

같은 색깔인 칸이 상하좌우로 인접하여 4개 이상 있다면 모두 터트려줍니다.

......
......
......
......
......
......
......
......
.Y....
.YG...
..YG..
..YGG.

더이상 터질 수 있는 뿌요가 없다면

중력에 의해 공중에 있는 뿌요는 밑으로 떨어지게 됩니다.

......
......
......
......
......
......
......
......
......
..G...
.YYG..
.YYGG.

다시 터트리고 채워주고 반복하면서

터트리는 과정을 몇번 할 수 있는지 세면 되는 문제입니다.

2.접근방법[알고리즘]

이 문제는 시뮬레이션 문제로 두가지 과정을 구현해주면 됩니다.

1. 뿌요 터트리기

2. 뿌요 떨어트리기

뿌요 터트리기는 BFS를 돌면서 같은 뿌요가 있다면 몇개있는지 세주고 4개 이상 있다면

같은 뿌요들을 저장해준뒤 char '.'로 바꿔주면 쉽게 구현할 수 있습니다.

뿌요 떨어트리기는 for문을 돌면서 맨 아래칸부터 시작하여 위칸을 돌면서

뿌요가 있다면 뿌요가 없는 맨 아래칸과 바꿔주면 됩니다.

처음 주어지는 INPUT이 중력에 의해 떨어진 상태가 아닐수도 있기 때문에

맨 처음 뿌요를 일단 다 떨어트리고 시작해야합니다.

3.문제풀이코드 C++

#include <iostream>
#include <algorithm>
#include <queue>
#include <memory.h>
using namespace std;

string arr[12];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

void fall() {
	for (int i = 0; i < 6; i++) {
		for (int j = 11; j >= 0; j--) {
			if (arr[j][i] == '.') {
				for (int k = j - 1; k >= 0; k--) {
					if (arr[k][i] != '.') {
						swap(arr[j][i], arr[k][i]);
						break;
					}
				}
			}
		}
	}
}


bool bomb() {
	bool ch[12][6];
	memset(ch, 0, sizeof(ch));
	queue<pair<int, int> > Q;
	bool bombed = false;

	for (int i = 0; i < 12; i++) {
		for (int j = 0; j < 6; j++) {

			if (ch[i][j] == 0 && arr[i][j] != '.') {

				vector<pair<int, int> > v;
				char color = arr[i][j];
				int cnt = 1;
				ch[i][j] = 1;
				v.push_back({ i,j });
				Q.push({ i,j });

				while (!Q.empty()) {
					int x = Q.front().first;
					int y = Q.front().second;
					Q.pop();


					for (int k = 0; k < 4; k++) {
						int nx = x + dx[k];
						int ny = y + dy[k];

						if (nx < 0 || nx >= 12 || ny < 0 || ny >= 6 || ch[nx][ny] == 1) continue;
						if (arr[nx][ny] == color) {
							cnt++;
							ch[nx][ny] = 1;
							Q.push({ nx,ny });
							v.push_back({ nx,ny });
						}
					}
				}

				if (cnt >= 4) {
					bombed = true;
					for (int k = 0; k < v.size(); k++) {
						arr[v[k].first][v[k].second] = '.';
					}
				}
			}
		}
	}

	return bombed;
}



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


	for (int i = 0; i < 12; i++) {
		cin >> arr[i];
	}
	// 필드에 뿌요를 모두 두고 일단 떨어트린다. 
	fall();

	//1.터트린다 - 개수 0이면 끝
	//2. 내린다
	//1.2 반복
	int ans = 0;

	while (1) {
		if (bomb()) {
			ans++;
			fall();
		}
		else {
			break;
		}
	}

	cout << ans << '\n';

	return 0;
}

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

1.문제설명

폭탄은 3초가 지나야 터진다.

폭탄이 터지면 폭탄이 있던 자리와 인접한 상하좌우칸이 .이 된다.

폭탄이 터지는 인접 상하좌우에 폭탄이 있을 경우 상하좌우에 있던 폭탄은 그냥 사라진다.

2.접근방법

3초가 되는 폭탄을 따로 배열이나 벡터에 저장했다가

각각 터트려야 쉽게 구현할 수 있다.

만약 3초가 지난 폭탄을 따로 저장하지 않고 순차적으로 터트릴 경우

인접한 3초 폭탄이 사라져 다른 결과를 얻게 된다.

다음 표에서 3이 써있는 폭탄은 이제 터지는 폭탄이라고 두고

O는 아직 터지지 않는 폭탄이라 생각하자.

그냥 무지성으로 3인 폭탄을 for문으로 돌며 터트리면 다음과 같은 결과를 얻는다

오른쪽에 있던 3폭탄이 터지지 못하고 그냥 묻혀버리고 만다.

다른 벡터에 3인 폭탄의 좌표를 모두 저장한 후 벡터에서 for문을 돌면서 터트리면 

이런 옳은 결과를 얻을 수 있다.

많은 시뮬레이션 문제에서 이렇게 정보를 저장한 후 실행하는 방법이 유용하게 쓰인다.

단순히 순차적으로 돌다보면 문제가 생기는 경우가 많다.

3.문제풀이코드 C++

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

int r, c, n, T;

int a[201][201];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };


void print() {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (a[i][j] == -1) {
				cout << '.';
			}
			else cout << 'O';
		}
		cout << '\n';
	}
}

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

	cin >> r >> c >> n;

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			char tmp;
			cin >> tmp;
			if (tmp == 'O') {
				a[i][j] = 0;
			}
			else {
				a[i][j] = -1;
			}
		}
	}
	
	if (T == n) {
		print();
		return 0;
	}


	T++;
	// 첫 1초 아무것도 안함 
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (a[i][j] == 0) {
				a[i][j]++;
			}
		}
	}
	if (T == n) {
		print();
		return 0;
	}

	
	T++;
	//2초 모든칸 폭탄 설치 
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			a[i][j]++;
		}
	}
	if (T == n) {
		print();
		return 0;
	}



	while(T<n) {

		T++;
		vector<pair<int, int> > v;
		
	
		// 아무것도 안함 
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (a[i][j] >= 0) a[i][j]++;
				if (a[i][j] == 3) {
					v.push_back({ i,j });
				}
			}
		}


		for (int i = 0; i < v.size(); i++) {
			a[v[i].first][v[i].second] = -1;
			for (int k = 0; k < 4; k++) {
				int nx = v[i].first + dx[k];
				int ny = v[i].second + dy[k];
				if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
				a[nx][ny] = -1;
			}
		}

		v.clear();
		if (T == n) break;


		T++;


		// 폭탄 설치 
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				a[i][j]++;
				if (a[i][j] == 3) v.push_back({ i,j });
			}
		}
		for (int i = 0; i < v.size(); i++) {
			a[v[i].first][v[i].second] = -1;
			for (int k = 0; k < 4; k++) {
				int nx = v[i].first + dx[k];
				int ny = v[i].second + dy[k];
				if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
				a[nx][ny] = -1;

			}
		}


	}

	
	print();

	return 0;
}

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

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

int r, c, t, arr[51][51], cleaner;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };


struct Dust {
	int x, y, q;
};


int ans() {
	int cnt = 0;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (arr[i][j] > 0) {
				cnt += arr[i][j];
			}
		}
	}
	return cnt;
}


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

	cin >> r >> c >> t;


	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == -1) {
				cleaner = i;
			}
		}
	}

	int clean_up = cleaner - 1;
	int clean_down = cleaner;

	//1.미세먼지 확산
	//2. 공기 청정기 이동 
	for (int T = 1; T <= t; T++) {

		vector<Dust> d;

		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (arr[i][j] >= 5) {
					d.push_back({ i,j,arr[i][j] });
				}
			}
		}

		//확산 
		for (int i = 0; i < d.size(); i++) {
			int spread = 0;
			if (d[i].q >= 5) {
				for (int k = 0; k < 4; k++) {
					int nx = d[i].x + dx[k];
					int ny = d[i].y + dy[k];

					if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
					if (arr[nx][ny] == -1)continue;
					arr[nx][ny] += (d[i].q / 5);
					spread++;

				}
				arr[d[i].x][d[i].y] -= (d[i].q / 5) * spread;
			}
		}

		// 공기청정기 작동 
		for (int i = clean_up - 1; i >= 0; i--) {
			arr[i + 1][0] = arr[i][0];
		}

		for (int i = clean_down; i < r; i++) {
			arr[i][0] = arr[i + 1][0];

		}

		for (int i = 0; i < c-1; i++) {
			arr[0][i] = arr[0][i + 1];
			arr[r - 1][i] = arr[r - 1][i + 1];
		}

		for (int i = 0; i < clean_up ; i++) {
			arr[i][c - 1] = arr[i + 1][c - 1];
		}

		for (int i = r-1; i > clean_down; i--) {
			arr[i][c - 1] = arr[i - 1][c - 1];
		}

		for (int i = c - 1; i > 1; i--) {
			arr[clean_up][i] = arr[clean_up][i - 1];
			arr[clean_down][i] = arr[clean_down][i - 1];
		}
		arr[clean_up][1] = 0;
		arr[clean_down][1] = 0;


		arr[clean_up][0] = -1;
		arr[clean_down][0] = -1;


	}

	int ans = 0;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (arr[i][j] > 0) ans += arr[i][j];
		}
	}

	cout << ans << '\n';

	return 0;
}

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

1. 문제설명

낚시왕이 되는 일은 꽤 어려운 일인지도 모릅니다.

어부는 오른쪽 열로 한칸 씩 이동하면서 

어부가 서있는 열에서 가장 가까운 상어를 잡습니다.

상어는 어부가 한칸 움직일 때마다 각각의 방향과 속도로 움직입니다.

만약 모든 상어가 움직인 후 같은 칸에 상어가 두마리 있을 경우 크기가 큰 상어만 남습니다.

어부가 끝까지 이동한 후 잡은 상어의 크기 합을 출력하면 됩니다.

2.접근방법[알고리즘]

이 문제를 해결하기 위해 특별히 필요한 알고리즘은 없습니다.

문제에서 제시한 조건 대로 구현하면 됩니다.

1. 어부가 오른쪽 열로 한칸 움직이고 가장 가까운 상어를 잡는다.

2. 상어 모두 각각 움직인다.

3. 겹치는 상어가 있으면 크기가 큰 것만 남긴다.

상어의 움직임을 구현하는 게 이 문제의 핵심입니다.

Input

상어의 정보는 다섯 정수 r, c, s, d, z (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000) 로 이루어져 있다. (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다.

전체 격자판 최대 크기는 100*100인데

상어의 속도는 1000이 최댓값이기 때문에

1000을 그대로 사용한다면 불필요한 움직임이 많이 포함됩니다.

상어가 열이나 행을 왕복하는데 필요한 거리는 r, c 값에 따라 고정되어 있기 때문에

연산을 통해 속도를 빼줄 수 있습니다.

if (d <= 2) s %= (r - 1) * 2;
else s %= (c - 1) * 2;

(r-1)*2 번이나 (c-1)*2 번 왔다갔다 하면 상어가 제자리에 놓이기 때문에

불필요한 연산을 줄여줄 수 있습니다.

이 과정을 거치지 않으면 시간초과가 납니다.

3.문제풀이코드 C++

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

int r, c, m, ans;

struct Shark {
	bool isin = 0;
	int s = 0, d = 0, z = 0;
};

Shark ch[103][103];

int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,1,-1 };

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

	cin >> r >> c >> m;
	for (int i = 0; i < m; i++) {
		int a, b, s, d, z;
		cin >> a >> b >> s >> d >> z;

		//상어의 반복움직임 제거
		if (d <= 2) s %= (r - 1) * 2;
		else s %= (c - 1) * 2;

		ch[a][b] = { 1,s,d,z };
	}


	for (int i = 1; i <= c; i++) {

		Shark moved[103][103];

		//해당 열에서 상어 잡기 
		for (int j = 1; j <= r; j++) {
			if (ch[j][i].isin) {
				ans += ch[j][i].z;
				ch[j][i] = { 0,0,0,0 };
				break;
			}
		}

		// 상어 이동 
		for (int j = 1; j <= r; j++) {
			for (int k = 1; k <= c; k++) {
				if (ch[j][k].isin) {
					int nx = j;
					int ny = k;

					for (int q = 0; q < ch[j][k].s; q++) {
						if (ch[j][k].d == 1) {
							//벽 만난 경우 방향전환
							if (nx == 1) {
								ch[j][k].d = 2;
								q--;
								continue;
							}
							nx += dx[0];
							ny += dy[0];

						}
						else if (ch[j][k].d == 2) {
							if (nx == r) {
								ch[j][k].d = 1;
								q--;
								continue;
							}

							nx += dx[1];
							ny += dy[1];

						}
						else if (ch[j][k].d == 3) {
							if (ny == c) {
								ch[j][k].d = 4;
								q--;
								continue;
							}
							nx += dx[2];
							ny += dy[2];

						}
						else if (ch[j][k].d == 4) {
							if (ny == 1) {
								ch[j][k].d = 3;
								q--;
								continue;
							}
							nx += dx[3];
							ny += dy[3];
						}

					}
					// 같은 칸에 상어 두마리가 있는 경우
					// 크키가 큰 상어만 남긴다.
					if (moved[nx][ny].isin) {
						if (moved[nx][ny].z < ch[j][k].z) {
							moved[nx][ny] = { 1,ch[j][k].s,ch[j][k].d,ch[j][k].z };
						}
					}
					else {
						moved[nx][ny] = { 1,ch[j][k].s,ch[j][k].d,ch[j][k].z };
					}

				}
			}
		}
		// moved 배열에 있는 값을 ch배열로 복사해주고 
		// ch배열을 통해 어부가 이동한후 다시 계산하도록 해준다.
		memcpy(&ch, &moved, sizeof(moved));
	}

	cout << ans << '\n';
	return 0;
}

백준 17143번 낚시왕 테스트케이스 및 반례

50 50 19
4 9 21 1 999
50 50 4 4 500
50 49 222 3 200
50 48 12 2 45
50 47 36 1 900
2 3 20 3 444
4 8 4 2 49
3 3 40 4 50
2 2 460 2 4444
48 23 500 3 12
1 1 200 1 123
44 44 123 3 125
44 40 222 3 17
40 44 333 3 57
18 40 1 1 4
3 10 50 2 406
1 36 177 4 50
1 46 120 4 7
1 50 28 4 54

정답 7718