취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 8598번 문제인 Zając이다.
문제는 아래 링크를 확인하자.

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

체스의 나이트와 같은 움직임을 하는 토끼가 굴에 들어가기 위해 필요한 점프의 최소 횟수를 구하는 문제이다. 이와 같은 유형의 문제는 BFS를 이용해 칸의 수에 비례한 시간복잡도로 해결할 수 있다.

아래의 dr과 dc와 같은 배열을 이용하면 토끼의 움직임을 보다 편하게 구현할 수 있다.

아래는 제출한 소스코드이다.

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

int R, C, sR, sC, eR, eC;
string board[1000];
int dist[1000][1000];
int dr[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int dc[8] = {2, 1, -1, -2, -2, -1, 1, 2};

queue<pair<int, int>> que;
void bfs() {
    dist[sR][sC] = 1;
    que.push(make_pair(sR,sC));
    while (!que.empty()) {
        int r = que.front().first, c = que.front().second; que.pop();
        for (int i = 0; i < 8; i++) {
            int rr = r + dr[i], cc = c + dc[i];
            if (rr<0 || rr>=R || cc<0 || cc>=C || dist[rr][cc] || board[rr][cc] == 'x') continue;
            dist[rr][cc] = dist[r][c] + 1;
            que.push(make_pair(rr, cc));
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> R >> C;
    for (int r = 0; r < R; r++) cin >> board[r];
    
    for (int r = 0; r < R; r++){
        for (int c = 0; c < C; c++){
            if (board[r][c] == 'z') sR = r, sC = c;
            else if (board[r][c] == 'n') eR = r, eC = c;
        }
    }
    
    bfs();
    
    if (dist[eR][eC]) cout << dist[eR][eC] - 1;
    else cout << "NIE";
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 8673번 문제인 Krany이다.
문제는 아래 링크를 확인하자.

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

물의 온도가 목표하는 정도가 될 때까지 현재 물이 나오고 있는 수도꼭지 중 가장 차가운 물이 나오는 수도꼭지부터 하나씩 차례대로 잠그는 것으로 문제를 해결하자.

물이 얼어있는 수도꼭지에서는 물이 나오고있지 않음에 유의하자. 또한 모든 나오는 물이 목표하는 온도보다 낮다면 조건을 만족시키게끔 수도꼭지를 틀어둘 수 없음에 유의하자.

아래는 제출한 소스코드이다.

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

int N, W, total, totalcnt;
priority_queue<int, vector<int>, greater<>> pq;
int ans;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> W;
    for (int i = 0; i < N; i++) {
        int x; cin >> x;
        if (x > 0) {
            total += x, totalcnt++;
            pq.push(x);
        }
    }
    
    while (totalcnt && total < W * totalcnt) {
        total -= pq.top();
        pq.pop();
        totalcnt--, ans++;
    }
    
    if (totalcnt) cout << ans;
    else cout << "NIE";
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 6005번 문제인 Cow Pinball이다.
문제는 아래 링크를 확인하자.

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

구슬이 어떤 못을 쳤을 때 그 시점까지 점수를 최대한 많이 얻으려면 이전 행의 가능한 양쪽의 못 중 더 많은 점수를 얻어올 수 있는 못을 치고 와야 함을 관찰하자.

위와 같은 점화관계를 이용해 dp로 문제를 해결할 수 있다. 각 행의 못마다 규칙적으로 번호를 매겨 복잡하지 않게 dp를 구현해주자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int R;
int arr[26][26];
int ans;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> R;
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= r; c++) {
			cin >> arr[r][c];
			arr[r][c] += max(arr[r - 1][c - 1], arr[r - 1][c]);
		}
	}

	for (int c = 1; c <= R; c++) ans = max(ans, arr[R][c]);

	cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11909번 문제인 배열 탈출이다.
문제는 아래 링크를 확인하자.

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

주어진 배열의 각 칸에 도달하는 최소 비용은 (왼쪽 칸에 도달하는 최소비용 + 그 칸에서 지금 칸으로 이동할 때 필요한 비용)과 (위쪽 칸에 도달하는 최소비용 + 그 칸에서 지금 칸으로 이동할 때 필요한 비용) 두 값 중 작은 값이 됨을 관찰하자. 

위의 점화관계를 이용해 dp로 문제를 해결할 수 있다.

이전 행이나 열이 없는 경우 등에 대한 특별한 예외처리가 필요없게끔 아래와 같이 주어진 배열의 위와 왼쪽으로 행을 하나씩 추가해 구현을 편하게 해보자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;
int arr[2223][2223];
int dp[2223][2223];

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

	cin >> N;
	
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) cin >> arr[r][c];
	}

	arr[1][0] = arr[0][1] = 1000000007;
	for (int r = 2; r <= N; r++) dp[r][0] = 1000000007;
	for (int c = 2; c <= N; c++) dp[0][c] = 1000000007;

	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			int val1 = dp[r - 1][c] + max(arr[r][c] - arr[r - 1][c] + 1, 0);
			int val2 = dp[r][c - 1] + max(arr[r][c] - arr[r][c - 1] + 1, 0);
			dp[r][c] = min(val1, val2);
		}
	}

	cout << dp[N][N];
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 21318번 문제인 피아노 체조이다.
문제는 아래 링크를 확인하자.

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

1 이상 N 미만의 정수 i에 대하여 arr[i]를 'i + 1번 악보보다 i번 악보가 어렵다면 1, 그렇지 않으면 0'로 정의하자. 이 때 각 쿼리가 요구하는 값은 배열 arr의 구간합으로 생각할 수 있다.

배열 arr이 업데이트되는 일이 없으므로 prefix sum 배열을 만들어 문제를 해결하자. 이를 구현할 때 N개의 악보를 살펴볼 때 살펴봐야 하는 arr값의 수는 N - 1개가 되므로 인덱스의 관리에 유의하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, Q;
int arr[100001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> arr[i];
	for (int i = 1; i < N; i++) {
		if (arr[i] > arr[i + 1]) arr[i] = 1;
		else arr[i] = 0;
		arr[i] += arr[i - 1];
	}

	cin >> Q;
	while (Q--) {
		int L, R; cin >> L >> R;
		cout << arr[R - 1] - arr[L - 1] << '\n';
	}
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 16401번 문제인 과자 나눠주기이다.
문제는 아래 링크를 확인하자.

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

주어진 과자들로 길이 K의 과자들을 만들 수 있는 개수를 f(K)라 하자. 그리고 이 때 f(K)는 단조감소함을 관찰하자.

주어진 문제는 f(K)의 값이 M 이상인 K의 최댓값을 찾는 문제로 볼 수 있고 f(K)는 단조감소하므로 문제의 답을 이진탐색을 통해 찾아낼 수 있다. 이를 구현해 문제를 해결하자.

아래는 제출한 소스코드이다.

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

int M, N;
int arr[1000000];
int L = 0, R = 1000000000;

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

	cin >> M >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];
	while (L < R) {
		ll cnt = 0;
		int mid = (L + R) / 2 + 1;
		for (int i = 0; i < N; i++) cnt += arr[i] / mid;

		if (cnt < M) R = mid - 1;
		else L = mid;
	}

	cout << L;
}