Alkon 3주차 챌린지
(6/6)
또 2등에 있다. 이번에는 D번에서 막히면서 느려져버렸다.
A번 아카라카 2 (32652, B3)
풀이
연속 부분 문자열로 AKARAKA를 n개 만드는 문제이다.
AKA가 뒤에 3개 있으니 계속해서 RAKA를 붙이면 만들 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m;
cin >> n;
cout << "AKARAKA";
for(int i=0;i<n-1;i++){
cout << "RAKA";
}
return 0;
}
생일 맞추기 (28358, B1)
풀이
모든 366개의 날짜를 돌면서 가능한 날짜인지 확인해주면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
char ch;
bool flag=0;
cin >> t;
while(t-->0){
int ans=0;
vector<int> v(10, 0);
for(int i=0;i<10;i++){
cin >> v[i];
}
for(int i=1;i<=12;i++){
if(i==1 || i==3 || i==5 || i==7 || i==8 || i==10 || i==12)b=31;
else if(i==2)b=29;
else b=30;
for(int j=1;j<=b;j++){
if(j<10)c=i*10+j;
else c = i*100+j;
flag = 0;
while(c){
if(v[c%10]){
flag=1;
}
c/=10;
}
if(!flag){
ans++;
}
}
}
cout << ans << '\n';
}
C번 이상한 하노이 탑 (15500, S2)
풀이
하노이 탑인데 규칙이 없는 하노이 탑이다.
어떻게든 해서 마지막에 큰 것이 아래로 간 상태를 만들면 된다.
스택으로 하노이탑 모형을 만들어서 찾는 값을 찾을 때까지 옮기면서 빼고
찾으면 3번째에 넣어주는 과정을 거치면 된다.
이 때 첫번째에 가장 큰게 있는지 두번째에 가장 큰게 있는지에 대한 정보를 배열로 저장한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
char ch;
bool flag=0;
cin >> n;
vector<bool> s1_ch(n+1,0);
stack <int> s1, s2;
for(int i=0;i<n;i++){
cin >> a;
s1.push(a);
s1_ch[a]=1;
}
int cnt=0;
vector<string> vs;
while(n){
if(s1_ch[n]){ //s1스택에 있으면
if(s1.top()==n){
s1_ch[s1.top()]=0;
s1.pop();
vs.push_back("1 3");
n--;
}
else{
s2.push(s1.top());
s1_ch[s1.top()]=0;
s1.pop();
vs.push_back("1 2");
}
}
else{
if(s2.top()==n){
s2.pop();
vs.push_back("2 3");
n--;
}
else{
s1.push(s2.top());
s1_ch[s2.top()]=1;
s2.pop();
vs.push_back("2 1");
}
}
}
cout << vs.size() << '\n';
for(int i=0;i<vs.size();i++){
cout << vs[i] << '\n';
}
return 0;
}
D번 시계 맞추기 (27532, G5)
풀이
조정이 안된 시계가 N개 주어지고, n분마다 시계를 찍은 결과가 나온다.
우선 아날로그 시계라는 조건 때문에 시간은 00:00부터 11:59까지로 720개다
그런데 주어지는 시계의 개수가 N개이기에 각각의 차이를 구하면 N^2이다.
브포로 전부 확인하면 1500*1500*720은 한참 시간 초과가 발생한다.
우선 각각의 시간은 전부 확인을 해야하기에 720번은 돌고, 어떻게 줄이지 고민하다
i를 720까지 돌리고, j는 N번 돌려서 각 시계마다 시간-i*j를 해서 check 배열에 넣었다.
이미 나온 시간이라면 ans를 증가하지 않고, 처음일때만 ans를 증가시킨다.
그렇게 1부터 720까지 확인을 해서 ans의 최솟값이 정답이 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
char ch;
bool flag=0;
cin >> n;
int mx = 1e9;
string s;
vector<int> time(n);
for(int i=0;i<n;i++){
cin >> s;
time[i] = int(s[0]-48)*600 + int(s[1]-48)*60 + int(s[3]-48)*10 + int(s[4]-48);
// moduler 720
}
int mi;
for(int i=1;i<=720;i++){
int ans=0;
vector<bool> check(720, 0);
for(int j=0;j<n;j++){
b = (time[j]-(i*j))%720;
if(b<0)b+=720;
if(check[b]==0){
check[b]=1;
ans++;
}
}
mi = min(mi, ans);
}
cout << mi;
return 0;
}
E번 마슈 반데드와 마법사의 격자판 (33151, G3)
풀이
N과 coin이 주어지고, NxN 격자판에 붙어 있는 칸은 동전 개수 차이가 1이 되도록 놓는다.
한 번 해보면 쉽게 생각할 수 있는데, 우선 N이 홀수와 짝수일때를 나눠야 한다.
우선 짝수일 때 가능한 최소 동전은 N*N/2이다.
또, 홀수개의 동전을 조건에 맞춰 놓을 수 없다.
주어진 동전이 N*N/2보다 크고, 짝수개라면 동전을 놓지 않은 칸에 2개씩 놔주면 된다.
N이 홀수라면
1
2
3
0 1 0
1 0 1
0 1 0
1
2
3
1 0 1
0 1 0
1 0 1
이렇게 동전이 짝수일 때와 홀수일 때를 모두 커버할 수 있다
위와 똑같이 N*N/2개 이상의 동전이 주어지기만 하면 된다.
동전의 개수가 많아지면 깔 수 있는 동전은 나누기 연산으로 구해줘야 한다.
남은 동전이 N*N/2~N*N/2*3 개가 되도록 나누기를 해서 미리 격자판에 깔면 빠르게 풀 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
char ch;
bool flag=0;
cin >> n >> m;
if(m<n*n/2){
cout << "-1";
return 0;
}
a = m%(n*n);
b = m/(n*n);
if(a<n*n/2){
a+=n*n;
b-=1;
}
vector<vector<int>> board(n, vector<int>(n, b));
if(n%2==1){
if(a%2==0){
a-=(n*n/2);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if((i+j)%2==1){
board[i][j]++;
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if((i+j)%2==0){
if(a==0)break;
board[i][j]+=2;
a-=2;
}
}
if(a==0)break;
}
}
else if(a%2==1){
a-=(n*n/2);
a-=1;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if((i+j)%2==0){
board[i][j]++;
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if((i+j)%2==1){
if(a==0)break;
board[i][j]+=2;
a-=2;
}
}
if(a==0)break;
}
}
}
if(n%2==0){
if(a%2==1){
cout << "-1";
return 0;
}
else{
a-=(n*n/2);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if((i+j)%2==0){
board[i][j]++;
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if((i+j)%2==1){
if(a==0)break;
board[i][j]+=2;
a-=2;
}
}
if(a==0)break;
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(j<n-1)
cout << board[i][j] << ' ';
else cout << board[i][j];
}
cout << '\n';
}
return 0;
}
F번 동전 쌍 뒤집기 (32034, P5)
풀이
애드훅 문제라서 규칙을 찾는 것이 중요한 문제였다.
우선 뒷면이 짝수개가 나와야지 답이 있고, 0개이면 뒤집을 필요가 없으니 0이다.
뒷면 동전을 뒤집어서 앞면으로 만들려면 뒷면 동전 사이의 동전 개수가 짝수개여야 한다.
그러므로 뒷면 동전이 나온 위치를 저장해놓고, 우선 맨 처음은 stack에 넣는다.
그 다음 나온 위치가 stack의 top과 짝수개 떨어져 있으면 사이에 있는 만큼 ans에 더해주고
홀수개 떨어져 있으면 그 위치를 stack에 넣어준다.
이 과정을 반복하면 답이 나온다.
동전의 개수가 백만개라 ans가 int범위를 초과할 수 있다는 것을 놓쳐서 몇 번 틀렸다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
long long ans;
string s;
cin >> t;
while (t-->0) {
vector<int> v;
cin >> n;
cin >> s;
ans = 0;
for (int i=0;i<s.length();i++) {
if (s[i] == 'T') { //뒷면이 나온 위치를 저장
v.push_back(i);
}
}
if (v.size()%2!=0) { //뒷면이 홀수개면 불가능
cout << "-1\n";
}
else if (v.size()==0) {
cout << "0\n";
}
else { //뒷면 짝수
stack<int> st;
for (int i=0;i<v.size();i++) {
if (st.empty()) { //비었으면 일단 넣고
st.push(i);
continue;
}
int k = st.top();
if ((v[i]-v[k])%2==0) { //사이의 동전 개수가 홀수개면 또 넣고
st.push(i);
}
else {
ans += (v[i]-v[k]);
st.pop();
}
}
if (!st.size()) cout << ans << '\n';
else cout << "-1\n";
}
}
return 0;
}
보고 어이없던 풀이가 하나 있어서 기록해놓는다.
풀이는 출제자인 bubbler 님의 블로그에서 가져왔다.
출처 : blog.bubbler.blue/posts/boj-problems/32034/
에디토리얼 별해 2 (XOR 기반 풀이)
짝수 번째 동전을 모두 뒤집고, 가능한 조작을 다음과 같이 바꾼다.
두 이웃한 동전이 서로 다른 면을 보일 때 두 동전을 뒤집는다. 그러면 원래 문제의 조건에서 뒤집을 수 있는 위치와 새로운 상황에서 뒤집을 수 있는 위치가 모두 일치한다.
또한, 서로 다른 면이 보이는 이웃한 두 동전을 뒤집는 것은 T를 이웃한 H로 한 칸 이동하는 것으로 볼 수 있고, HHHHHH…인 최종 상태는 HTHTHT…로 바뀐다. 따라서, 새로운 조건에서의 T들을 최소한의 횟수로 움직여 모두 짝수 번째 자리에 놓는 문제로 환원이 되며, 이는 매우 쉽게 풀 수 있다.
이 풀이를 알고 있는 사람들 사이에서는 010101…로 XOR하는 풀이로 알려져 있는 듯하다.
이러한 풀이가 사용되는 다른 문제로 15941. TV 동물 농장, 18346. 업과 격의 그래프 등이 언급되었는데,
15941이 공교롭게도 UCPC 기출이어서 대회에서 빠질 뻔했다.
알아두면 어딘가에 유용하게 사용할 수 있을 것 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
char ch;
bool flag=0;
cin >> t;
while(t-->0){
cin >> n;
string s;
cin >> s;
long long ans=0;
int j=1;
for(int i=0;i<n;i++){
if((s[i]=='T')^(i&1)){
ans+=abs(i-j);
j+=2;
}
}
if(j>=n && j<=n+1){
cout << ans << '\n';
}
else cout << "-1\n";
}
return 0;
}