굳건하게

문제 : https://www.acmicpc.net/problem/16933

BFS

● BFS 탐색을 진행하는데 벽을 몇 번 부수고 현재 지점에 도달했는지 체크하기위해 3차원 visited 배열을 사용하면 된다.

● visited[x][y][w] := (x, y) 지점에 w만큼의 벽을 부수고 도달

● 현재 지점에서 이동할 다음 칸이 벽이 아니고 방문하지 않았다면 큐에 push.

    현재 지점에서 이동할 다음 칸이 벽이라면

    - 낮인 경우, 이동할 칸에 현재 벽 부순 횟수 + 1 상태로 방문한 적이 없다면 큐에 push

    - 밤인 경우, 이동할 칸에 현재 벽 부순 횟수 + 1 상태로 방문한 적이 없다면 큐에 현재 위치를 push

#include<iostream>
#include<queue>

using namespace std;

struct node {
	int x, y, t, w; // x좌표 y좌표 벽부순횟수 시간
};

int N, M, K, dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };
char map[1000][1001];
bool visited[1000][1000][11] = {};

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

	cin >> N >> M >> K;
	for (int i = 0; i < N; i++)
		cin >> map[i];

	queue<node> q;
	q.push({ 0, 0, 0, 0});
	visited[0][0][0] = 1;

	int ans = -1;
	while (!q.empty()) {
		int curX = q.front().x, curY = q.front().y;
		int curTime = q.front().t, curW = q.front().w;
		q.pop();
		if (curX == N - 1 && curY == M - 1) {
			ans = curTime + 1;
			break;
		}
		for (int i = 0; i < 4; i++) {
			int nextX = curX + dx[i], nextY = curY + dy[i];
			if (!(0 <= nextX && nextX < N && 0 <= nextY && nextY < M))
				continue;
			if (map[nextX][nextY] == '0' && !visited[nextX][nextY][curW]) {
				visited[nextX][nextY][curW] = 1;
				q.push({ nextX, nextY, curTime + 1, curW });
			}
			if (map[nextX][nextY] == '1' && curTime % 2 == 0 && curW + 1 <= K && !visited[nextX][nextY][curW + 1]) {
				visited[nextX][nextY][curW + 1] = 1;
				q.push({ nextX, nextY, curTime + 1, curW + 1});
			}
			if (map[nextX][nextY] == '1' && curTime % 2 == 1 && curW + 1 <= K && !visited[nextX][nextY][curW + 1]) {
				q.push({ curX, curY , curTime + 1, curW });
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

문제 : https://www.acmicpc.net/problem/12851

DP BFS

BFS 탐색에 DP를 적용해서 문제를 해결했습니다.

● DP[X] := start에서 시작해 X 지점에 오는데 필요한 최소 이동 횟수.

● 내가 현재 지점(x) 에서 점프 횟수가 y일 때, 다음에 이동할 지점의 DP 값이 y + 1 보다 작으면 최소 이동 횟수가 아니므로 점프를 하지 않고, 또 y + 1이 현재 정답(end에 오는데 필요한 최소 점프 횟수) 보다 크면 최소 이동 횟수가 아니므로 점프를 하지 않아도 됩니다.

#include<iostream>
#include<queue>
#define INF 99999999
using namespace std;

int dp[200001] = {};

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

	int N, K, ans = INF, cnt = 0;
	cin >> N >> K;

	queue<pair<int, int>> q;
	q.push({ N, 0 });
	for (int i = 0; i < 200001; i++)
		dp[i] = INF;

	while (!q.empty()) {
		pair<int, int> cur = q.front(); 
		q.pop();
		if (cur.first == K) {
			ans = min(ans, cur.second);
			if (ans == cur.second)
				cnt++;
		}
		if (0 <= cur.first - 1 && cur.second + 1 <= dp[cur.first - 1] && cur.second + 1 <= ans){
			dp[cur.first - 1] = cur.second + 1;
			q.push({ cur.first - 1, cur.second + 1 });
		}
		if (cur.first + 1 <= K && cur.second + 1 <= dp[cur.first + 1] && cur.second + 1 <= ans){
			dp[cur.first + 1] = cur.second + 1;
			q.push({ cur.first + 1, cur.second + 1 });
		}
		if (cur.first * 2 <= 200000 && cur.second + 1 <= dp[cur.first * 2] && cur.second + 1 <= ans){
			dp[cur.first * 2] = cur.second + 1;
			q.push({ cur.first * 2, cur.second + 1 });
		}
	}
	cout << ans << '\n' << cnt;
	return 0;
}

문제 : 2018 KAKAO BLIND RECRUITMENT [3차] n진수 게임

문자열 수학 구현 

 Input의 크기가 작아 단순 구현으로 해결할 수 있는 문제입니다. 

 숫자 0부터 1씩 키워가며 N진법으로 표현한 후, N진법으로 표현된 수를 다시 한 자리씩 순회하며 m명의 친구들에게 하나씩 배당해준다. 이때, 튜브의 차례라면 answer에 concat 해준다.

#include <string>
#include <vector>

using namespace std; 

string solution(int n, int t, int m, int p) {
	char list[16] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B','C', 'D', 'E' , 'F' };
	string answer = "";
	p--;
	int curN = 0, curP = 0;
	while (answer.length() < t) {
		string temp = "";
		int tempN = curN;
		do { // curN을 N진법으로 표현하자.
			temp += list[tempN % n];
			tempN /= n;
		} while (tempN);

		for (int i = temp.length() - 1; i >= 0; i--) {
			if (curP % m == p && answer.length() < t)
				answer += temp[i];
			curP = (curP + 1) % m;
		}
		curN++;
	}
	return answer;
}

문제 : https://www.acmicpc.net/problem/1300

이분탐색

 N x N 행렬의 i 번 째 행을 보면 i번 째 구구단인 것을 알 수 있습니다. 따라서, i번 째 행에서 어떤 값 x 보다 작거나 같은 수는 x / i 를 통해 구할 수 있습니다. 주의할 점은 예를 들어 N이 5이면 3번 째 행은 3 6 9 12 15 가 된다. 이때 18보다 작거나 같은 수를 18 / 3 으로 구해버리면 하나가 더 카운트 된다. 즉 i번 째 행에서 얻을 수 있는 갯수는 최대 N개 이므로 i번 째 행에서 x 보다 작거나 같은 수는 min( x / i , N ) 으로 구할 수 있다.

따라서, 다음과 같은 식을 만들 수 있다.

F(x) := N x N 행렬에서 x 보다 작거나 같은 숫자의 갯수

       := 1 ~ N 까지의 수로 x 를 나눈 값과 N 중 더 작은 값을 다 더한다.

이때, 정의상 F(x) 는 단조증가함수가 되므로 이분탐색을 이용할 수 있다.

#include<iostream>
#include<algorithm>

using namespace std; 

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int N, K;
	cin >> N >> K;

	int result = 0;
	int left = 1, right = K;
	while (left <= right) {
		int mid = (left + right) / 2;
		int cnt = 0;
		for (int i = 1; i <= N; i++) { // cnt에는 mid보다 작거나 같은 애들 담김.
			cnt += min(mid / i, N);
		}
		 if (cnt < K) // mid로는 아직 부족함.
			left = mid + 1;
		else{ // mid로 충분할 수도 있고, 더 작아질 수도 있으므로 일단 저장.
			result = mid;
			right = mid - 1;
		 }
	}
	cout << result << '\n';
	return 0;
}