문제 설명: 시계의 3개의 침이 눈금(tick) 단위로 주어질 때 정확한 시간을 "시간 분 초 나노초"로 출력하라. 시간은 정확히 자정~정오 사이의 시간(0~12)이다. 각 침 중 어느것이 시침, 분침, 초침인지는 알 수 없으며, 주어진 3개의 값은 각각 특정 침을 기준으로 움직인 눈금 수이다.
시침은 매 나노초마다 정확히 1 눈금씩 움직임
분침은 매 나노초마다 정확히 12 눈금씩 움직임
초침은 매 나노초마다 정확히 720 눈금씩 움직임
1 눈금 = 1/12 * 1/1e10 도
1초 = 10^9 나노초
입력: (0 ≤ A ≤ B ≤ C < 360×12×10^10)
출력: h m s nano
접근법: 이 문제는 순서 상관없이 상대적으로 움직인 눈금 수를 받아서 (1) 순서를 맞추고 (2) 눈금 수로 원래 시간을 맞춰야 하는 문제이다. 먼저 순서를 맞추는 방법부터 고민해보자. 입력으로 받은 A, B, C는 각각 시침, 분침, 초침과 매칭되어야 하는데 3개를 나열하는 순열은 3! = 6 으로 굉장히 작은 수임을 알 수 있다. 따라서 시침/분침/초침에 각각 3개의 눈금 수를 놓아보면 될 것이다.
순서를 어떻게 맞출 것인가
시침, 분침, 초침은 각각 1의 배수, 12의 배수, 720의 배수이다.
0 0 0 <- 맨 처음 눈금 1 12 720 <- 1나노초 뒤 2 24 1440 <- 2나노초 뒤 ... x 12x 720x <- x나노초 뒤
그러나 회전하는 경우도 주어지기 때문에 맨 처음 눈금의 상태를 t라고 하자. 그럼 x나노초 뒤의 시침, 분침, 초침은
t + x = y1 t + 12x = y2 t + 720x = y3
를 가지게 된다. 여기서 2개의 수식을 이용하면 x와 t를 알아낼 수 있다.
t + x = y1 - t + 12x = y2 ---------------- -11x = y1 - y2 => x = (y2 - y1) / 11 => t = y1 - x
그러나, x를 계산할 때 이 시계가 회전된 상태임을 포함해야 정확히 t를 계산할 수 있게 된다. 1회전의 눈금 수는 M = 360×12×10^10 이며, 두 눈금의 차이 y2 - y1 은 매 회전마다 값은 같기 때문에 diff를 미리 계산해놓는다.
여기서 y2 < y1 인 경우에 대해 y2 += M 을 해준다.
회전은 1시간 단위로 11번 회전해야 시침 y1으로 시작 상태를 구할 수 있다. 여기서 360도 회전할 때 눈금 수가 360×12×10^10 = M 이기 때문에 M/11, 2M/11, 3M/11 ... 11M/11 을 매 회전마다 diff/11 에 더해준다.
diff/11 + i*M/11 = (diff + i*M) / 11
단 여기서 11x = y2 - y1 도 만족해야 되기 때문에 위의 결과에서 11의 배수인지 검사하는 조건문을 추가해야 한다.
그리고 입력으로 받은 A, B, C는 각각 y1, y2, y3 중 하나에 매칭되어야 한다. 3개의 수식에 대해 모두 일치하면 그 때의 X값을 시간 단위로 바꾸어 준다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll M = 360*12*1e10;
const ll TICK_UNIT[3] = {1, 12, 720};
const ll MAX_NANO = 1e9;
void solve() {
vector<ll> in(3);
for (int i = 0; i < 3; i++) cin >> in[i];
do {
ll diff = in[1] - in[0];
if (diff < 0) diff += M; // in[1] + M - in[0]
for (int i = 0; i < 12; i++) {
ll x = diff + i * M;
if (x % 11 != 0) continue;
x /= 11;
ll t = in[0] - x;
if (t < 0) t += M; // t = in[0] + M - x
bool good = true;
for (int i = 0; i < 3 and good; i++)
if ((t + TICK_UNIT[i] * x) % M != in[i])
good = false;
if (good) {
ll divider[3] = {MAX_NANO, 60, 60};
vector<ll> ans;
for (int i = 0; i < 3; i++) {
ans.push_back(x % divider[i]);
x /= divider[i];
}
ans.push_back(x);
for (auto it = ans.rbegin(); it != ans.rend(); it++)
cout << *it << " ";
cout << endl;
return;
}
}
} while (next_permutation(in.begin(), in.end()));
}
int main() {
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
Subtransmutation
문제 설명: i번 금속을 파괴해서 (i-A)번 금속과 (i-B)번 금속을 만들 수 있다. 단 i > A 이거나 i > B 이어야 한다. 그렇지 않다면 단순히 파괴만 된다. 만약 A <= i <= B 일 경우 (i-A)번 금속만 만들어질 것이다. 입력으로 만들어야 할 금속 번호와 각 금속의 개수 및 A, B가 주어질 때 입력으로 주어진 모든 금속을 만들 수 있는 금속 번호 중 최솟값을 찾아야 한다. 만약 만들 수 없다면 IMPOSSIBLE을 출력
금속은 아래 그림처럼 계속해서 분할할 수 있다. 예를 들어, A=1, B=2일 때 4번 금속은 최종적으로 1번 금속 1개와 2번 금속 2개를 생성한다.
입력
1 <= N <= 20
1 <= Ui <= 20 : 각 금속 번호(=i)의 개수
1 <= Un
2 <= U1 + U2 + ... + Un
Test Set 1: A = 1, B = 2
Test Set 2: 1 <= A < B <= 2
출력: 최소 금속 번호
첫번째 접근법: 금속을 가장 많이 만들어야 하는 최악의 경우는 20번 금속을 20회 만드는 것이다. i번 금속을 분할해서 i-1번 금속과 i-2번 금속을 만들 때 생성된 두 금속을 분할하면 반드시 i-1번 금속은 i-2번 금속을 포함한다. Test Set 1 에서는 A=1, B=2 이기 때문에 20번 금속을 20회 만드려면 금속 번호가 최소 27이어야 한다. 1~19번 금속 번호를 생성하는 것까지 생각해본다면 넉넉잡아 금속 번호를 29번까지만 검사해보면 될 것이다. 검사는 단순히 A와 B를 빼주면서 분할되는 모든 금속번호를 카운트하는 것으로, 각 금속 번호에서 1씩 빼주면(분할의 최악의 경우) 전체 경우의 수는 2^20 = 1048576 인데 이를 29번 시도하니 29 * 1,048,576 = 30,408,704 만큼 반복문을 돌게 된다. 따라서 충분히 시간 안에 실행할 수 있다.
21 => 20번 금속 1개
22 => 20번 금속 2개
23 => 1 + 2 = 3개
24 => 2 + 3 = 5개
25 => 3 + 5 = 8개
26 => 5 + 8 = 13개
27 => 8 + 13 = 21개
28 => 13 + 21 = 34개
29 => 21 + 34 = 55개
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, A, B;
vector<int> U;
void divide(int n, vector<int>& v) {
if (n <= 0) return;
if (n < v.size()) {
if (v[n] > 0) {
v[n]--;
return;
}
}
divide(n-A, v);
divide(n-B, v);
}
void solve() {
cin >> N >> A >> B;
int maxunits = 0, ans = -1;
U = vector<int> (N+1);
for (int i = 1; i <= N; i++) {
cin >> U[i];
if (U[i] > maxunits) {
maxunits = U[i];
ans = i + min(A, B);
}
}
while (ans < 30) {
vector<int> v = U;
divide(ans, v);
// 분할했을 때 요구된 모든 금속을 생성할 수 있는 경우
if (all_of(v.begin(), v.end(), [](int x) { return x <= 0; })) {
cout << ans << endl;
return;
}
ans++;
}
cout << "IMPOSSIBLE" << endl;
}
int main() {
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
두번째 접근법: Test Set2는 A와 B가 1~20 사이의 숫자로, 최악의 경우 A=19, B=20일 때 20번 금속을 20개 생성하는 것이다. 19번 금속부터 20씩 증가할 때 분할 시 20번 금속의 개수가 1씩 증가한다. 따라서 20개를 만드려면 금속 번호가 최대 19 + 20 * 20 = 419 는 되어야 한다.
39 => 20번 금속 1개
40 => 20번 금속 1개
41 ~ 58 => 0개
59 => 2개
60 => 1개
61 ~ 78 => 0개
79 => 3개
80 => 1개
...
19 + 20 * k => k개
단, Test Set 1에서 했던 브루트 포싱은 419번 하게 되면 시간 초과가 발생하게 된다. 즉, 다른 방식으로 금속을 분할해서 검사해야 한다.
해설에 적힌 아이디어는 M번 금속을 분할할 때 M-A번 금속과 M-B번 금속의 개수를 "M번 금속 개수 - U[M]"만큼 더해주면서 M을 1씩 줄여주고 계속 분할해간다. 단, M번 금속 개수 < U[M] 일 경우 분할해도 개수가 모자르기 때문에 더 이상 분할하는 것이 의미가 없다. 브루트-포싱과의 차이점은 이 방식은 반복문이 M회 돌기 때문에 시간 복잡도가 굉장히 작다는 것이다. 그럼에도 개수를 모두 확인할 수 있어서 최대 419번 금속까지 시도해보고 그래도 분할되지 않는다면 IMPOSSIBLE을 출력하면 된다.
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int N, A, B;
const int MAXNUM = 419;
int U[MAXNUM];
bool canPossible(int m) {
vector<int> v(m+1, 0);
v[m] = 1;
for (int i = m; i >= 1; i--) {
if (v[i] < U[i]) return false;
int x = v[i] - U[i];
if (i > A) v[i-A] += x;
if (i > B) v[i-B] += x;
}
return true;
}
void solve() {
cin >> N >> A >> B;
int ans = -1;
memset(U, 0, sizeof(U));
for (int i = 1; i <= N; i++) {
cin >> U[i];
if (U[i] > 0) ans = i;
}
ans += A;
while (ans < MAXNUM) {
if (canPossible(ans)) {
cout << ans << endl;
return;
}
ans++;
}
cout << "IMPOSSIBLE" << endl;
}
int main() {
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
Digit Blocks
문제 설명: N개의 타워를 지어야 하는데, 각 타워는 최대 B개의 블록만 쌓을 수 있다. i번째 블록은 밑에서부터 i번째 임을 의미하며, 밑에서부터 블록을 쌓을 수 있다. 각 블록은 숫자가 한 면에 존재하며 항상 앞 쪽에 숫자 면이 존재한다. 블록을 쌓을 때는 B개 미만으로 있는 타워에 위에 쌓거나, 아니면 타워가 N개 미만일 때 새로운 타워의 첫번째 블록으로 쌓을 수 있다. 전부 다만든 뒤에 타워의 점수는 왼쪽 타워부터 오른쪽 타워 순으로 위에서부터 숫자를 붙여서 만든 정수들의 합이다. 예를 들어, bottom [ ... ] top 으로 타워를 표기할 때 [ 3 2 1 ], [ 5 4 3 ], [ 6 9 0 ] 으로 쌓인 3개의 타워는 123 + 345 + 96 = 564 를 점수로 갖는다. 각 블록마다 숫자는 0~9 사이이며, 서로 독립적으로 랜덤으로 균등하게 생성된다. 정답이 맞도록 하기 위해, 테스트 케이스의 모든 점수의 합은 적어도 P여야 한다.
입력으로 T, N, B, P 가 주어지며, P는 테스트셋을 통과하기 위해 필요한 최소 점수 총합이다.
이 문제는 interactive problem 으로, 처음에 놓아야할 블록에 적힌 숫자 D가 주어지고 프로그램은 놓길 원하는 타워의 번호 (1~N)를 응답한다.
마지막 테스트 케이스를 제외하고 위 과정을 반복하고 나면 즉시 다음 테스트 케이스가 진행된다. 마지막 테스트 케이스가 끝나면 judge 프로그램은 총 점수가 P 이상이면 1 아니면 -1을 응답한다.
위의 조건들 중 하나라도 잘못된 입력을 줄 경우 즉시 -1을 응답한다.
입력
T <= 50
N <= 20
B <= 15
D = 0 ~ 9
Test Set 1: P <= 860939810732536850
Test Set 2: P <= 937467793908762347
각 테스트 케이스당 N*B 번 judge 를 실행한다.
첫번째 접근법: 점수 총합을 최대화해야 하는데, 매우 극단적으로 생각해보면 9보다 작은 수는 맨 아래에 위치시키고 9를 맨 위에 놓는 방법이 있다. 그러나 항상 9가 B번째 위치에 올 수는 없는데 그럴 경우 현재 상태에서 가장 높은 타워(height <= B-1)의 위에 놓는다.
#include <iostream>
#include <vector>
#include <algorithm>
#define pb push_back
#define sz(c) (int)(c).size()
using namespace std;
typedef long long ll;
int T, N, B;
ll P;
int put(int D, vector<vector<int>>& towers) {
int loc;
if (D < 9) {
for (int i = 0; i < N; i++) {
int h = sz(towers[i]);
if (h < B-1) {
loc = i+1;
break;
}
if (h < B) loc = i+1;
}
} else {
int idx = 0, highest = -1;
for (int i = 0; i < N; i++) {
int h = sz(towers[i]);
if (h < B and h > highest) {
highest = h;
idx = i;
}
}
loc = idx+1;
}
towers[loc-1].pb(D);
return loc;
}
void solve() {
vector<vector<int>> towers(N, vector<int> (0));
for (int i = 0, D; i < N*B; i++) {
cin >> D;
cout << put(D, towers) << endl;
}
}
int main() {
cin >> T >> N >> B >> P;
while (T--)
solve();
int correct;
cin >> correct;
return 0;
}
두번째 접근법: 위의 전략은 그리디 알고리즘이다. 두번째 테스트셋부터 정확도를 확 올려야 하는데 확률을 계산하기에는 복잡할 것 같아서 위의 방법에서 디테일(?)을 추가했다. 테스팅 툴을 돌려보면 D >= 8 일 때 높은 위치에 놓을 경우 첫번째 테스트셋을 통과한다. 즉, 각 타워의 상위 2개의 블록에 8과 9를 적절히 배치하는 것으로 정확도를 올릴 수 있을 것 같았다.
주의할 점은 put() 함수에서 D < 8 조건문에서 블록을 놓을 때 B-2 까지만 놓을 수 있도록 해야 하는 것이다.
또한, 상위 2칸만 남았을 때 8보다 9가 항상 더 위에 오도록 하려면 높은 타워 중 2번째로 높은 타워에 8을 배치해야 한다. 따라서 높이 배열 2칸을 준비하고 8이 놓일 자리가 없을 경우에만 9가 놓일 자리에 8을 놓는다.
상위 2칸이 남지 않았더라도 항상 가장 높은 위치에 9를, 그 다음 높은 위치에 8을 놓도록 해야 한다.
#include <iostream>
#include <vector>
#include <algorithm>
#define pb push_back
#define sz(c) (int)(c).size()
using namespace std;
typedef long long ll;
int T, N, B;
ll P;
int put(int D, vector<vector<int>>& towers) {
int loc;
if (D < 8) {
for (int i = 0; i < N; i++) {
int h = sz(towers[i]);
if (h < B-2) {
loc = i+1;
break;
}
if (h < B) loc = i+1;
}
} else {
int idx[2] = {0, 0}, highest[2] = {-1, -1};
for (int i = 0; i < N; i++) {
int h = sz(towers[i]);
if (h < B and h > highest[0]) {
highest[0] = h;
idx[0] = i;
}
if (h < B-1 and h > highest[1]) {
highest[1] = h;
idx[1] = i;
}
}
if (D == 8 and highest[1] == -1) idx[1] = idx[0];
loc = idx[(D == 9 ? 0 : 1)] + 1;
}
towers[loc-1].pb(D);
return loc;
}
void solve() {
vector<vector<int>> towers(N, vector<int> (0));
for (int i = 0, D; i < N*B; i++) {
cin >> D;
cout << put(D, towers) << endl;
}
}
int main() {
cin >> T >> N >> B >> P;
while (T--)
solve();
int correct;
cin >> correct;
return 0;
}
