Alkon 1주차 챌린지
(6/6)
이번에 학교 알고리즘 동아리 들어갔는데 매주 챌린지가 있다길래 다 풀어보려고 한다.
문제 난이도는 각각 B4, B2, S4, G5, G3, P4였는데 나름 풀만한 난이도였던 것 같다.
A번 심부름 가는 길 (5554, B4)
풀이
이동하는 시간이 초 단위로 4개가 주어지고, 그걸 다 더한 다음 분, 초 단위로 나타내면 끝이다.
쉽게 풀라고 1시간도 안넘는다는 조건이 있으니 다 더하고 /60, %60 해주면 된다.
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, k, t;
int o_1, o_2;
cin >> a >> b >> c >> d;
int total=0;
total+= (a+b+c+d);
cout << total/60 << '\n' << total%60;
return 0;
}
거스름돈 (5585, B2)
풀이
1000엔을 냈을 때 거스름 돈을 받는데 총 지폐의 양을 구한다.
단위는 500, 100, 50, 10, 5, 1엔이 있고 그리디하게 큰 것부터 빼면 된다.
사실 동전0(11047, S4)랑 완전 같은 문제 같은데 왜 하나는 브론즈고 하나는 실버지..
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, k, t;
int o_1, o_2;
cin >> n;
int mo = 1000-n;
int ans=0;
while(mo){
if(mo>=500){
mo-=500;
ans++;
}
else if(mo>=100){
mo-=100;
ans++;
}
else if(mo>=50){
mo-=50;
ans++;
}
else if(mo>=10){
mo-=10;
ans++;
}
else if(mo>=5){
mo-=5;
ans++;
}
else if(mo>=1){
mo-=1;
ans++;
}
}
cout << ans;
return 0;
}
C번 수강 바구니 (17488, S4)
풀이
딱히 풀이랄게 없는 순수 구현문제다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, k, t;
int o_1, o_2;
cin >> n >> m;
vector<int> v(m+1); //정원
for(int i=1;i<=m;i++){
cin >> v[i];
}
vector<vector<int>> success(n+1);
vector<vector<int>> sin(m+1);
for(int i=1;i<=n;i++){ //1차
while(1){
cin >> a;
if(a==-1)break;
sin[a].push_back(i);
}
}
for(int i=1;i<=m;i++){
if(sin[i].size() <= v[i]){ //자리가 있으면
for(int j=0;j<sin[i].size();j++){
success[sin[i][j]].push_back(i);
}
v[i] -= sin[i].size();
sin[i].clear();
}
}
for(int i=1;i<=n;i++){ //2차
while(1){
cin >> a;
if(a==-1)break;
sin[a].push_back(i);
}
}
for(int i=1;i<=m;i++){
if(sin[i].size() <= v[i]){ //자리가 있으면
for(int j=0;j<sin[i].size();j++){
success[sin[i][j]].push_back(i);
}
v[i] -= sin[i].size();
}
}
for(int i=1;i<=n;i++){
sort(success[i].begin(), success[i].end());
}
for(int i=1;i<=n;i++){
if(success[i].size()==0){
cout << "망했어요";
}
for(int j=0;j<success[i].size();j++){
if(j==success[i].size()-1)cout << success[i][j];
else cout << success[i][j] << ' ';
}
cout << '\n';
}
return 0;
}
D번 주사위 쌓기 (2116, G5)
풀이
주사위 전개도가 주어지고 주사위를 쌓을 때 옆면의 합이 가장 크게 되도록 만들면 된다.
평범한 주사위처럼 양쪽의 합이 7이 아니고, 쌓을 때 맞닿은 면의 숫자가 같게 해야 한다.
쌍을 맞추는게 귀찮을 것 같아 함수로 따로 만들고, 만약 윗, 밑이 5랑 6이라면 옆면은 4이고,
하나가 6이면 옆면은 5, 6이 없으면 옆면이 6이 오게 된다.
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
using namespace std;
int ssang(int n){
if(n==0)return 5;
if(n==5)return 0;
if(n==1)return 3;
if(n==3)return 1;
if(n==2)return 4;
if(n==4)return 2;
return 0;
}
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
long long n, m, t;
cin >> n;
vector<vector<int>> v(n, vector<int>(6));
for(int i=0;i<n;i++){
for(int j=0;j<6;j++){
cin >> v[i][j];
}
}
int ma = -1;
for(int k=1;k<=6;k++){
int total = 0;
int ceil = 0; //천장
int floor = 0; // 바닥
for(int j=0;j<6;j++){ //바닥 index 찾기
if(v[0][j]== k){
floor = j;
ceil = ssang(j);
if(v[0][floor] == 6 || v[0][ceil] == 6){
if((v[0][floor] == 5 && v[0][ceil] == 6) || (v[0][floor] == 6 && v[0][ceil] == 5)){
total += 4;
}
else total += 5;
}
else{
total+=6;
}
break;
}
}
int aa = v[0][ceil];
for(int i=1;i<n;i++){
for(int j=0;j<6;j++){ //바닥 index 찾기
if(v[i][j]== aa){
floor = j;
ceil = ssang(j);
if(v[i][floor] == 6 || v[i][ceil] == 6){
if((v[i][floor] == 5 && v[i][ceil] == 6) || (v[i][floor] == 6 && v[i][ceil] == 5)){
total += 4;
}
else total += 5;
}
else{
total+=6;
}
break;
}
}
aa = v[i][ceil];
}
ma = max(ma, total);
}
cout << ma;
return 0;
}
E번 세 친구 (10096, G3)
풀이
펠린드롬 문제를 투 포인터로 풀었던 것처럼 접근했다.
우선 주어진 문자열의 길이가 짝수이면 성립할 수 없기에 바로 종료를 한다.
생각을 해보면 왼쪽이 하나 더 크게 잘라보고, 오른쪽이 하나 더 크게 잘라 본 다음
각각의 경우에 대해서 삽입한 문자의 종류가 하나일 수 밖에 없다.
그리고 왼쪽을 더 크게 잘랐을 때 S는 오른쪽 문자열이고, 반대의 경우는 S가 왼쪽 문자열이다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
long long n, m, t;
string s;
cin >> n;
cin >> s;
if(n%2==0){
cout << "NOT POSSIBLE\n";
return 0;
}
string s1, s2;
s1 = s.substr(0, n/2+1); //왼쪽 더 크게
s2 = s.substr(n/2+1, n);
int chk = 0;
string ans1 = s2; // 답이 될 문자
int l=0, r=0;
while(r<n/2){
if(s1[l]!=s2[r] && chk == 0){
chk = 1;
ans1 = s2;
l++;
}
else if(s1[l]!=s2[r] && chk == 1){
ans1 = "";
break;
}
else{
l++;
r++;
}
}
s1 = s.substr(0, n/2); //왼쪽 더 크게
s2 = s.substr(n/2, n);
chk = 0;
string ans2 = s1; // 답이 될 문자
l=0, r=0;
while(l<n/2){
if(s1[l]!=s2[r] && chk == 0){
chk = 1;
r++;
}
else if(s1[l]!=s2[r] && chk == 1){
ans2 = "";
break;
}
else{
l++;
r++;
}
}
if(ans1=="" && ans2=="")cout << "NOT POSSIBLE";
else if(ans1==ans2) cout << ans1;
else if(ans1=="" && ans2!="") cout << ans2;
else if(ans1!="" && ans2=="") cout << ans1;
else cout << "NOT UNIQUE";
return 0;
}
F번 K번째 좋은 문자열 (14056, P4)
풀이
플레티넘 문제여서 조금 쫄아서 미루다 도전했는데, 처음 생각한 아이디어가 맞았다.
우선 주어지는 문자열의 길이가 150이고, 좋은 문자열의 기준이 꽤 복잡하기 때문에 문자열에서
나올 수 있는 좋은 문자열의 개수가 생각보다 적다는 것에 착안했다.
그래서 ()부터 시작해서 (()*n)의 형태를 찾을 때마다 좋은 문자열 vector에 넣어줬고
다시 vector에서 하나씩 꺼내면서 꺼낸 문자열로 만들어지는 좋은 문자열을 찾아 vector에 추가하며
bfs에서 큐 끝까지 찾는 것처럼 브포를 돌렸다.
만약 시간 초과가 나면 좋은 문자열 찾는 것을 dp로 바꾸는게 좋을 것 같다?고 생각을 했는데
다행히도 너무 여유있게 20ms로 풀렸다.
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
#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <queue>
#include <set>
#include <algorithm>
#include <math.h>
using namespace std;
string s;
bool good_chk(string s1, string s2){ //s2에 원하는 문자열이 있는지 확인
int l = 0;
int r = 0;
while(1){
if(l>s1.size()){ //있음
return 1;
}
if(r>s2.size()){ //없음
return 0;
}
if(s1[l]==s2[r]){
l++;
r++;
}
else{
r++;
}
}
}
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
vector<string> v;
cin >> s >> n;
if(good_chk("()", s)){
v.push_back("()");
}
for(int i=0;i<v.size();i++){
int num = 1;
while(1){
string ch_s = "(";
for(int j=0;j<num;j++){
ch_s += v[i];
}
ch_s += ")";
if(good_chk(ch_s, s)){
v.push_back(ch_s);
}
else break;
num++;
}
}
sort(v.begin(), v.end());
if(n>v.size()){
cout << -1;
}
else{
cout << v[n-1];
}
return 0;
}