백준 스터디 10주차 - 발표

Q1. 2798 블랙잭 > 문제 링크

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

int main() {
	int n, m;
	cin >> n >> m;

	vector<int> num_list;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		num_list.push_back(num);
	}

	int res = 0;
	int sub = m;

	for (int i = 0; i < n - 2; i++) {
		for (int j = i+1; j < n - 1; j++) {
			for (int k = j+1; k < n; k++) {
				int sum = num_list[i] + num_list[j] + num_list[k];
				if ((m - sum < sub) && (sum <= m)) {
					res = sum;
					sub = m - sum;
				}
			}
		}
	}

	cout << res << endl;
}

반복문을 이용하여 입력받은 모든 수의 합을 계산한 후
그 값이 주어진 수 m보다 작거나 같고,
'이때까지의 계산값 중 합이 m과 가장 차이가 적게 날 때의 차'와 '현재 계산값과 m의 차'를 비교했을 때 현재 계산값과 m의 차가 더 작은지를 체크한다.
만약 두 조건을 모두 만족시킬 시 이를 결과값으로 삼고, 차 또한 갱신하여 저장해두는 과정을 반복한다.
그 후 모든 값에 대해 계산을 완료했을 때 저장된 결과값을 출력한다.

---

Q2. 12581 숨바꼭질2 > 문제 링크

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

int main() {

	int n, k;
	cin >> n >> k;
	
	int ans_time = 0, ans_cnt = 0;
	queue<pair<int, int>> q; // <위치, 시간> 저장
	int check[100001] = { 0, };

	q.push({ n,0 });

	while (!q.empty()){
		int now = q.front().first;
		int time = q.front().second;
		q.pop();
		check[now] = true;

		if (now == k) {
			if (ans_cnt == 0) { 
				// 완전히 처음 방문한 경우
				ans_time = time;
				ans_cnt++;
			}
			else if (ans_time == time) {
				// 이미 최소시간으로 방문한 경우, 최소 시간으로 방문했는지 추가 확인 필요
				ans_cnt++;
			}
		}


		if (now - 1 >= 0 && !check[now - 1]) {
			q.push({ now - 1,time + 1 });
		}
			
		if (now + 1 < 100001 && !check[now + 1]) {
			q.push({ now + 1,time + 1 });
		}
			
		if (2 * now < 100001 && !check[2 * now]) {
			q.push({ 2 * now,time + 1 });
		}
	}

	cout << ans_time << '\n' << ans_cnt << '\n';
}

문제를 요약하면 수빈이와 동생의 위치가 주어질 때 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 문제이다.
수빈이의 위치와 동생의 위치가 같아질 때까지 최단경로를 탐색 해 시간과 방법의 수를 구하는 문제이므로, BFS로 문제를 풀었다.

우선 기본적으로 큐에서 원소를 pop 할 때 visited 배열을 true로 바꿔준다. push 하는 시점에 visited를 갱신하면 중복 방문이 불가능하기 때문이다.

이후의 과정은 동생을 만난 상황과 만나지 않은 상황으로 나뉘는데,
동생과 수빈이가 만나지 않은 경우에는 수빈이는 1초에 현재 위치 +1 or -1, or x2 만큼 이동할 수 있으므로, 수빈이가 이동 가능한 경로를 모두 큐에 담는다.
이 때 각 원소에서 시간은 지금 방문해있는 노드까지 도달하기 걸린 시간 + 1초로 계산하고, 위치는 각 상황에 맞게(+1, -1, x2) 갱신하여 넣는다.
그리고 동생과 수빈이의 위치가 같아졌을 때(만났을 때),
처음으로 현재 위치와 동생의 위치가 같아지게 된 상황에서는 그 상황이 최단 시간일 것이므로 ans_time에 저장한다.
이후에도 현재 위치와 동생의 위치가 같아지면 동생을 찾는 다른 방법이 더 있는 것이므로, 시간을 비교해서 최단 시간에 방문한 경로인지를 체크하여 해당하는 경우 방법의 수또한 추가한다.
이렇게 모든 방문을 마친 후 결과값을 출력한다.