Alkon 2주차 챌린지
(6/6)
저번이랑 똑같은 사진 같지만 다른 주차 다른 문제이다.
A번 오버플로우와 모듈러 (15818, B3)
풀이
주어지는 숫자들을 모두 곱한 값에 모듈러 연산을 한 값을 출력하는 문제이다.
간단하게 곱하는 모든 숫자들에 모듈러 연산을 하며, 마지막 결과에도 한번 더 해주면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 >> m;
long long ans=1;
for(int i=0;i<n;i++){
cin >> t;
ans = ans * (t%m);
ans%=m;
}
cout << ans;
return 0;
}
슈팅 연습 (32930, S5)
풀이
주어진 범위에서 현재 위치에서 가장 먼 총알을 하나씩 찾아서 계산하면 된다.
이미 선택한 좌표는 check 배열을 통해서 없애주고, 브포로 돌려서 풀었다.
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;
cin >> n >> m;
int x = 0, y = 0;
vector<pair<int, int>> v;
for(int i=0;i<n+m;i++){
cin >> a >> b;
v.push_back({a,b});
}
vector<bool> check(n+m, 0);
int ans = 0;
int aa = 0, bb, cc, dd;
for(int j=0;j<m;j++){
for(int i=0;i<n+j;i++){
if(check[i])continue;
if(aa<(x - v[i].first)*(x-v[i].first) + (y-v[i].second)*(y-v[i].second)){
aa = (x - v[i].first)*(x-v[i].first) + (y-v[i].second)*(y-v[i].second);
bb = v[i].first;
cc = v[i].second;
dd = i;
}
}
x = bb;
y = cc;
ans += aa;
check[dd]=1;
aa=0;
}
cout << ans;
return 0;
}
C번 팰린드롬 애너그램 (30458, 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
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;
string s;
cin >> s;
vector<int> check(26, 0);
for(int i=0;i<s.size();i++){
if(s.size()%2==1){
if(i == s.size()/2) continue;
}
check[s[i]-'a']++;
}
int flag = 0;
for(int i=0;i<26;i++){
if(check[i]%2==1) flag = 1;
}
if(flag){
cout << "No";
}
else cout << "Yes";
return 0;
}
D번 No title (32763, G5)
풀이
인터랙티브 문제였다.
우선 붙어있는 각 숫자에 대해 곱하기를 해보면 붙어있는 글자의 부호가 같은지 다른지 알 수 있다.
그 다음 1, 2번 숫자의 부호가 같다면 더하기를 했을 때 양수라면 +, 음수라면 -로 특정할 수 있다.
만약 1, 2번 숫자의 부호가 다르다면 3번 숫자를 이용해 구할 수 있다.
만약 처음 결과가 -, - 라면 1번과 3번이 같고, 2번이 다른 것이므로 1, 3번 숫자와 +연산을 하면 되고
처음 결과가 -, +라면 2번과 3번의 부호가 같고, 1번이 다른 것이므로 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
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;
cin >> n;
vector<char> result(n, 0);
vector<char> ans(n+1, 0);
for(int i=1;i<n;i++){
cout << "? " << i << " * " << i+1 << endl;
cin >> result[i];
}
if(result[1]=='+'){
cout << "? " << 1 << " + " << 2 << endl;
cin >> ch;
ans[1] = ch;
}
else if(result[1]=='-' && result[2]=='-'){
cout << "? " << 1 << " + " << 3 << endl;
cin >> ch;
ans[1] = ch;
}
else{ //-, +일 때
cout << "? " << 2 << " + " << 3 << endl;
cin >> ch;
if(ch=='+')ans[1]='-';
else ans[1]='+';
}
for(int i=2;i<=n;i++){
if(result[i-1]=='-'){
if(ans[i-1]=='+')ans[i]='-';
else ans[i] = '+';
}
else{
ans[i]=ans[i-1];
}
}
cout << "! ";
for(int i=1;i<=n;i++){
cout << ans[i] << ' ';
}cout << endl;
return 0;
}
E번 직사각형 (16207, G3)
풀이
길이 범위가 작아서 배열에 전부 저장하는 방법을 사용했다.
가능한 가장 큰 길이끼리 곱하는 것이 이득이기 때문에 100000부터 반복문을 내려온다.
길이로 가능하려면 같은 숫자가 2개 있어야 하고, length[i][0]이 1이되면 length[i-1][1]에 넘겨준다.
최대 한 번만 1만큼 줄일 수 있으므로 2차원 배열로 따로 관리했다.
그 다음 똑같이 가능한 가장 긴 길이끼리 곱하는 과정을 반복하고 더하면 된다.
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;
cin >> n;
vector<vector<long long>> length(100001, vector<long long>(2,0));
for(int i=0;i<n;i++){
cin >> m;
length[m][0]++;
}
long long ans=0;
long long x=0, y=0;
for(int i=100000;i>=2;i--){
if(length[i][0]+length[i][1]>=2){
length[i][1]-=2;
if(length[i][1]<0){
length[i][0] += length[i][1];
length[i][1]=0;
}
if(x==0)x=i;
else if(y==0)y=i;
i++;
}
else if(length[i][0]==1){
length[i-1][1]++;
}
if(x!=0 && y!=0){
ans += x*y;
x=y=0;
}
}
cout << ans;
return 0;
}
F번 수들의 합 3 (2007, P3)
풀이
구현에서 헷갈려서 푸는 과정이 오래 걸렸다.
다른 사람들 풀이를 보니 배열보다 map을 쓰는게 더 효율적인 풀이였을 것 같다.
ans 배열이 우리가 구해야 하는 정답 배열이라고 하자.
아이디어는 주어진 배열을 정렬하면 처음 두 숫자는 각각 ans[0]+ans[1], ans[0]+ans[2]이다.
이제 ans[1]+ans[2]의 값을 안다면 계산을 통해서 ans[0], ans[1], ans[2]를 모두 구할 수 있다.
이렇게 그림을 그려보니 주어진 배열을 정렬했을 때 ans[1]+ans[2]의 값은 최소 n+1번안에 나온다.
왜냐하면 그 전에 올 수 있는 수는 ans[0]+ (ans[1]…ans[n-1]) 이기 때문이다.
이 정도면 충분히 브루트포스로 풀 수 있을 것 같다고 생각했다.
n+1번째까지 반복문을 돌면서 그 수가 ans[1]+ans[2]가 될 수 있는지 확인하는 것이다.
그러면 어떻게 가능한지 확인할 수 있을까?
그래서 vector
여기에 나온 숫자들을 모두 count하고, 나온 숫자를 모두 제거한다.
ans[0], ans[1], ans[2]를 구했다면 가능한 조합들을 remove 배열에서 빼준다.
ans[0]+ans[1], ans[0]+ans[2], ans[1]+ans[2]를 제외하고 남은 가장 작은 수는 ans[0]+ans[3]이다.
단순히 만들 수 있는 조합 중에서 ans[0]+ans[3]이 남은 가장 작은 수이기 때문이다.
우리는 ans[0]을 알고 있기에 ans[3]도 구할 수 있고, 이제 ans[0]~ans[3]을 이용한 모든 조합을 또 빼준다.
그러면 다음 남은 수는? ans[0]+ans[4]가 된다.
이렇게 ans[n]까지 구하면서 remove 배열에서 값을 전부 뺄 수 있다면 정답이 된다.
비슷한 문제가 몇 개 더 있던데 이거는 map으로 접근해서 풀어봐야겠다.
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
using namespace std;
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;
cin >> n;
//정렬하고 처음 2개는 (0,1), (0,2)임.
//마찬가지로 마지막 뒤는 (n-1, n), (n-2, n)임.
//최대 100, 받는 숫자는 4950
//그런데 (1,2)은 적어도 앞에서 101개 안에는 존재하게 됨.
//(1,2)을 알면 1, 2, 3을 알 수 있게 되고 그러면 연쇄적으로 알 수 있지 않나?
vector<int> v(n*(n-1)/2);
vector<int> remove(2000001, 0);
vector<int> remove2(2000001);
for(int i=0;i<n*(n-1)/2;i++){
cin >> v[i];
remove[v[i]+1000000]++;
}
sort(v.begin(), v.end());
vector<int> ans(n, 0);
if(n==2){ //2개면 따로 처리해야함.
cout << min(0, v[0]) << ' ' << max(0, v[0]); // 98퍼 반례임 음수가 들어올 수도 있네
return 0;
}
bool flag = 0;
for(int i=2;i<n;i++){
// 각각이 (1,2)인 경우를 고려
if((v[0]+v[1]-v[i])%2!=0){
continue;
}
flag = 1;
ans[0] = (v[0]+v[1]-v[i])/2;
ans[1] = v[0] - ans[0];
ans[2] = v[1] - ans[0];
//3개까지 구해놓기
int cnt = 2;
copy(remove.begin(), remove.end(), remove2.begin()); //시간이 괜찮나
if(ans[0]+ans[1]>1000000 || ans[1]+ans[2]>1000000 || ans[0]+ans[2]>1000000){
flag=0;
continue;
}
if(remove2[ans[0]+ans[1]+1000000]>0)remove2[ans[0]+ans[1]+1000000]--;
else {
flag=0;
continue;
}
if(remove2[ans[0]+ans[2]+1000000]>0)remove2[ans[0]+ans[2]+1000000]--;
else {
flag =0;
continue;
}
if(remove2[ans[1]+ans[2]+1000000]>0)remove2[ans[1]+ans[2]+1000000]--;
else {
flag=0;
continue;
}
int point = 0;
while(1){
if(cnt==n-1)break;
cnt++;
while(remove2[v[point]+1000000]==0){
point++;
}
ans[cnt] = v[point] - ans[0];
for(int j=0;j<cnt;j++){
if(ans[cnt]+ans[j]>1000000){
flag=0;
break;
}
if(remove2[ans[cnt]+ans[j]+1000000]>0){ //(0,1), (0,2), (1,2)를 지우면 다음은 무조건 (0,3)임.
remove2[ans[cnt]+ans[j]+1000000]--;
}
else{
flag =0;
break;
}
}
if(!flag)break;
}
if(cnt==n-1)break;
}
if(!flag){
cout << "Impossible\n";
}
else{
sort(ans.begin(), ans.end());
for(int i=0;i<n;i++){
cout << ans[i] << ' ';
}
}
return 0;
}