취미로 코딩하기

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

이번에 볼 문제는 백준 2780번 문제인 비밀번호이다.
문제는 아래 링크를 확인하자.

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

길이가 N(>2)이고 자리 i로 끝나는 비밀번호의 개수는 길이가 N-1이고 i와 인접한 칸에 적힌 비밀번호의 개수들의 합과 같음을 관찰하자.

위와 같은 점화관계를 이용해 1000까지의 문제의 답을 미리 구해두고, 각 N에 대해 답을 빠르게 출력해 문제를 해결하자.

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

#define MOD 1234567
#include <iostream>
using namespace std;

int T;
int dp[1001][10];

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

	for (int i = 0; i < 10; i++) dp[1][i] = 1;
	for (int n = 2; n < 1001; n++) {
		dp[n][0] = dp[n - 1][7] % MOD;
		dp[n][1] = (dp[n - 1][2] + dp[n - 1][4]) % MOD;
		dp[n][2] = (dp[n - 1][1] + dp[n - 1][3] + dp[n - 1][5]) % MOD;
		dp[n][3] = (dp[n - 1][2] + dp[n - 1][6]) % MOD;
		dp[n][4] = (dp[n - 1][1] + dp[n - 1][5] + dp[n - 1][7]) % MOD;
		dp[n][5] = (dp[n - 1][2] + dp[n - 1][4] + dp[n - 1][6] + dp[n - 1][8]) % MOD;
		dp[n][6] = (dp[n - 1][3] + dp[n - 1][5] + dp[n - 1][9]) % MOD;
		dp[n][7] = (dp[n - 1][4] + dp[n - 1][8] + dp[n - 1][0]) % MOD;
		dp[n][8] = (dp[n - 1][5] + dp[n - 1][7] + dp[n - 1][9]) % MOD;
		dp[n][9] = (dp[n - 1][6] + dp[n - 1][8]) % MOD;
	}

	cin >> T;
	while (T--) {
		int x; cin >> x;
		int ans = 0;
		for (int i = 0; i < 10; i++) ans += dp[x][i];
		cout << ans % MOD << '\n';
	}
}

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

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

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

이 문제는 주어지는 수열의 LIS(Longest Increasing Subsequence)의 길이를 구하는 문제이다. LIS 문제의 해법을 이용해 문제를 해결하자.

N의 크기가 작으므로 \(O(N^2)\) 해법으로도 충분히 문제를 해결할 수 있다.

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

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

int N;
ll arr[5000];
int dp[5000];
int ans;

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
		for (int j = 0; j < i; j++) {
			if (arr[j] < arr[i]) dp[i] = max(dp[i], dp[j]);
		}
		dp[i]++;

		ans = max(ans, dp[i]);
	}

	cout << ans;
}

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

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

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

(1,1)에서 출발해 (R,C)까지 이동할 때 가장 많은 금화를 모을 수 있는 경로를 찾는 문제이다.

(1,1)에서 출발해 (r,c)까지 이동하는 방법은 (r-1,c-1)을 경유하거나 (r,c-1)을 경유하거나 (r+1,c-1)을 경유하는 세 가지가 존재한다. 각 방법마다 해당 칸까지 이동하면서 모을 수 있는 금화의 최댓값을 비교해 (r,c)까지 이동하면서 모을 수 있는 금화 개수의 최댓값을 dp로 구해나가는 것으로 문제를 해결하자.

(1,1)에서 출발해 경유할 수 없는 칸((2,1) 등)에서 금화를 주워 최적의 경로를 잘못 구하는 일이 일어나지 않게끔 구현에 유의하자.

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

#include <iostream>
using namespace std;

int R, C;

int coins[102][101];
int dp[102][101];

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

	cin >> R >> C;
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) cin >> coins[r][c];
	}

	dp[1][1] = coins[1][1];

	for (int c = 2; c <= C; c++) {
		for (int r = 1; r <= R; r++) {
			for (int dr = -1; dr < 2; dr++) {
				dp[r][c] = max(dp[r][c], dp[r + dr][c - 1]);
			}
			if (dp[r][c]) dp[r][c] += coins[r][c];
		}
	}

	cout << dp[R][C];
}

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

이번에 볼 문제는 백준 6191번 문제인 Cows on Skates이다.
문제는 아래 링크를 확인하자.

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

주어지는 농장을 돌이 많지 않은 상하좌우 칸끼리 연결되어있는 그래프로 생각하면 주어진 문제는 농장의 (1,1) 칸에 대응되는 그래프의 노드에서 (R,C) 칸에 대응되는 그래프의 노드로 이어지는 경로를 찾는 문제가 된다. 경로의 존재성은 문제가 보장해주고 있으므로, bfs 등의 그래프 탐색 알고리즘을 이용해 경로를 찾아 문제를 해결하자.

이 때, 각 노드를 탐색할 때마다 해당 노드를 어떤 노드로부터 접근해왔는지를 기록해두자. 그리고 모든 탐색을 마친 다음 (R,C) 칸으로부터 탐색경로를 역추적해 문제의 답을 구하자.

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

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

int R, C;
string board[115];
pair<int, int> backtrack[115][79];
bool visited[115][79];

queue<pair<int, int>> que;
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };
void bfs() {
	que.push(make_pair(1, 1));
	visited[1][1] = 1;

	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (visited[rr][cc] || board[rr][cc] == '*') continue;
			visited[rr][cc] = 1;
			backtrack[rr][cc] = make_pair(r, c);
			que.push(make_pair(rr, cc));
		}
	}
}

vector<pair<int, int>> stk;
pair<int, int> p11 = make_pair(1, 1);

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

	cin >> R >> C;

	for (int c = -2; c < C; c++) board[0] += "*";
	for (int r = 1; r <= R; r++) {
		cin >> board[r];
		board[r] = "*" + board[r] + "*";
	}
	for (int c = -2; c < C; c++) board[R + 1] += "*";

	bfs();

	pair<int, int> cur = make_pair(R, C);
	while (cur != p11) {
		stk.emplace_back(cur);
		cur = backtrack[cur.first][cur.second];
	}

	cout << 1 << ' ' << 1 << '\n';
	while (!stk.empty()) {
		cout << stk.back().first << ' ' << stk.back().second << '\n';
		stk.pop_back();
	}
}

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

이번에 볼 문제는 백준 25399번 문제인 라그랑주님 수학에는 뺄셈도 있어요이다.
문제는 아래 링크를 확인하자.

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

음의 정수의 경우 양의 정수를 구성하는 방법에서 부호를 바꿔 답을 구할 수 있으므로 양의 정수들을 제곱수로 구성하는 방법을 알아보자.

먼저 주어진 수 \(N\)이 한 개의 제곱수의 합으로 나타날 수 있는지를 확인하자. 이는 주어진 수가 제곱수인지를 확인하는 것과 같다.

다음으로 주어진 수가 두 개의 제곱수의 합(또는 차)으로 나타날 수 있는지를 확인하자.

주어진 수가 두 개의 제곱수의 합으로 나타낼 수 있는지의 여부는 투포인터를 이용해 \(O(\sqrt{N})\)에 구할 수 있다.

모든 3 이상의 홀수의 경우 \((n+1)^2-n^2=2n+1\)로부터 두 제곱수의 차로 구할 수 있음을 알 수 있다.

4의 배수의 경우 \((2n+1)^2-(2n-1)^2=4n\)로부터 두 제곱수의 차로 구할 수 있음을 알 수 있다.

그 외의 경우(짝수이지만 4의 배수가 아닌 경우)는 두 제곱수의 차로는 구할 수 없다. 모든 제곱수는 \(4n\) 또는 \(4n+1\)꼴임을 상기하자.

남은 수는 두 제곱수의 합으로 나타낼 수 없는, 4의 배수가 아닌 짝수이다.이 경우 아무 홀수 제곱수를 먼저 더한 다음 그렇게 만들어진 홀수를 두 제곱수의 차로 나타내는 것으로 세 정수를 이용해 표현할 수 있다. 이 과정에서, 먼저 더한 홀수 제곱수를 다른 두 수를 찾을 때 재사용하지 않도록 유의하자.

마지막으로 0을 1개 이상의 제곱수들로 구성해 문제를 해결하자.

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

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

ll N; bool neg;
vector<ll> vec;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    
    if (N == 0) {
        cout << 3 << '\n' << "+ 5\n- 4\n- 3";
        return 0;
    }
    if (N == 2) {
        cout << 3 << '\n' << "+ 11\n+ 5\n- 12";
        return 0;
    }
    if (N == -2) {
        cout << 3 << '\n' << "- 11\n- 5\n+ 12";
        return 0;
    }
    
    if (N < 0) N *= -1, neg = 1;
    
    
    
    for (ll i = 1; i * i <= N; i++) {
        if (i * i == N) {
            if (neg) cout << 1 << '\n' << '-' << ' ' << i;
            else cout << 1 << '\n' << '+' << ' ' << i;
            return 0;
        }
        
        vec.emplace_back(i * i);
    }
    
    int L = 0, R = vec.size() - 1;
    while (L < R) {
        ll val = vec[L] + vec[R];
        if (val == N) {
            if (neg) cout << 2 << '\n' << '-' << ' ' << L + 1 << '\n' << '-' << ' ' << R + 1;
            else cout << 2 << '\n' << '+' << ' ' << L + 1 << '\n' << '+' << ' ' << R + 1;
            return 0;
        }
        
        if (val < N) L++;
        else R--;
    }
    
    if (N & 1) {
        ll x = N / 2 + 1, y = N / 2;
        if (neg) cout << 2 << '\n' << '-' << ' ' << x << '\n' << '+' << ' ' << y;
        else cout << 2 << '\n' << '+' << ' ' << x << '\n' << '-' << ' ' << y;
    }
    else if (N % 4 == 0){
        ll x = N / 4 + 1, y = N / 4 - 1;
        if (neg) cout << 2 << '\n' << '-' << ' ' << x << '\n' << '+' << ' ' << y;
        else cout << 2 << '\n' << '+' << ' ' << x << '\n' << '-' << ' ' << y;
    }
    else {
        N++;
        ll x = N / 2 + 1, y = N / 2;
        if (neg) cout << 3 << '\n' << '-' << ' ' << x << '\n' << '+' << ' ' << y << '\n' << '+' << ' ' << 1;
        else cout << 3 << '\n' << '+' << ' ' << x << '\n' << '-' << ' ' << y << '\n' << '-' << ' ' << 1;
    }
}

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

이번에 볼 문제는 백준 2731번 문제인 1379와 세제곱이다.
문제는 아래 링크를 확인하자.

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

먼저 길이가 n이고 1,3,7 또는 9로 끝나는 양의 정수 s에 대하여 s보다 길이가 짧거나 같은 양의 정수 중 세제곱의 마지막 n자리가 s와 같은 정수가 유일함을 수학적 귀납법을 이용해 간단히 살펴보자. 이 과정을 따라가면 그러한 정수를 구하는 방법을 알 수 있다.

n=1인 경우 s가 1, 3, 7, 9일 경우 각각 1, 7, 3, 9와 같이 세제곱하면 1의 자리가 s가 되는 한 자리 정수가 존재함을 알 수 있다.

n이 k 미만일 때 모든 길이가 n이고 1,3,7 또는 9로 끝나는 양의 정수 s에 대하여 s보다 길이가 짧거나 같고 세제곱의 마지막 n자리가 s와 같은 양의 정수를 유일하게 찾을 수 있다고 가정하자.

k자리 정수 s에 대하여 세제곱이 s의 마지막 k-1자리와 겹치는 마지막 자리를 갖는 유일한 k-1자리 수(leading zero 포함)를 tmp라 하자. 우리가 찾는 수는 tmp로 끝나야 한다는 사실은 자명하다.

이제 우리가 구하는 수의 k번째 자리 수를 x라 했을 때, \((10^{k - 1} x + tmp)^3\)의 전개식과 s의 마지막 k자리를 비교하면 어렵지 않게 x의 값이 유일함을 증명할 수 있다. 그리고 그 값 또한 구할 수 있다.

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

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

int T; ll N;
int num[11], ans[10], dgt;
int inv[10] = {0, 1, 0, 7, 0, 0, 0, 3, 0, 9};

void solve() {
    memset(ans, 0, sizeof(ans));
    memset(num, 0, sizeof(num));
    dgt = 0;
    cin >> N;
    
    if (N % 10 == 1) {
        num[0] = 1;
        ans[0] = 1;
    }
    else if (N % 10 == 3) {
        num[0] = 3, num[1] = 4, num[2] = 3;
        ans[0] = 7;
    }
    else if (N % 10 == 7) {
        num[0] = 7, num[1] = 2;
        ans[0] = 3;
    }
    else{
        num[0] = 9, num[1] = 2, num[2] = 7;
        ans[0] = 9;
    }
    
    dgt++, N /= 10;
    
    while (N) {
        int tmp = 0;
        for (int i = 0; i < dgt; i++){
            for (int j = 0; j < dgt; j++){
                for (int k = 0; k < dgt; k++){
                    if (i + j + k == dgt) tmp += ans[i] * ans[j] * ans[k];
                }
            }
        }
        int d = dgt;
        while (tmp && d < 10){
            num[d] += tmp % 10;
            if (num[d] > 9){
                num[d + 1] += num[d]/10;
                num[d] %= 10;
            }
            
            tmp /= 10, d++;
        }
        
        int x = N % 10 - num[dgt];
        if (x < 0) x += 10;
        ans[dgt] = (x * inv[ans[0]] * inv[ans[0]] * inv[3]) % 10;
        
        tmp = ans[dgt] * ans[0] * ans[0] * 3;
        d = dgt;
        while (tmp && d < 10){
            num[d] += tmp % 10;
            if (num[d] > 9){
                num[d + 1] += num[d] / 10;
                num[d] %= 10;
            }
            
            tmp /= 10, d++;
        }
        
        dgt++, N /= 10;
    }
    
    int i = dgt - 1;
    
    while (!ans[i]) i--;
    for (; i > -1; i--) cout << ans[i];
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> T;
    while (T--) solve();
}