백준 마라톤 (코스38)
(6/8)
사용자 수준에 맞춰서 문제를 랜덤으로 골라서 내주는 solved 랜덤 마라톤이다.
어느새 하다보니 38번째 코스에 도달했고, 실버 반, 골드 반이 나온다.
다 풀 수 있었는데 실수해서 시간내에 못 푼 것이 아쉽다.
D번은 기간 내에 풀었는데 왜 X처리가 된 것인지는 모르겠고..
골랜디 느낌으로 공부하기 재밌고, 곧 플레 문제도 1~2문제씩 나올 것 같다.
A번 Anti-Arithmetic Permutation (9703, B1)
풀이
size 50인 배열이 주어지고, i < j < k 에서 산술 순열인 ai, aj, ak가 있는지를 묻는다.
50밖에 안되므로 브포로 반복문 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
using namespace std;
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long a, b, c;
int n, m, t;
cin >> t;
a=0;
while(t-->0){
cin >> n;
a++;
vector<int> v(n);
for(int i=0;i<n;i++){
cin >> v[i];
}
int check=0;
for(int i=0;i<n-2;i++){
for(int j=i+2;j<n;j++){
for(int k=i+1;k<j;k++){
if(v[i]+v[j]==2*v[k]){
check=1;
break;
}
}
}
}
cout << "Case #" << a << ": ";
if(check)cout << "NO\n";
else cout << "YES\n";
}
return 0;
}
B번 월향, 비샹 (29336, S2)
풀이
운영진의 능력 배열이 주어지고, 운영진은 그 능력을 한 번만 써서 문제를 만들 수 있다.
하루마다 능력은 1 증가하고, 며칠까지 어느 수준 이상의 문제를 만들라는 조건이 주어진다.
그 조건을 지키며 만들 수 있는 문제 난이도의 최대치를 구하는 문제이다.
그리디하게 풀리는게 능력이 오르는 것은 하루마다 모두 +1이므로 능력을 최대한 안 쓰는게 중요하다.
그러므로 내림차순 정렬 후에, 필요할 때마다 앞부터 넣어주면 된다.
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
using namespace std;
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long a, b, c;
int n, m, t;
cin >> n >> m;
vector<long long> v(n);
vector<pair<long long, long long>> con(m);
for(int i=0;i<n;i++){
cin >> v[i];
}
sort(v.begin(), v.end());
for(int i=0;i<m;i++){
cin >> con[i].first >> con[i].second;
}
sort(con.begin(), con.end());
//이분 탐색인줄 알았는데 최대를 넣는게 이득이네?
long long ans=0;
int point = n-1;
for(int i=0;i<m;i++){
while(con[i].second > ans){
if(point<0){
cout << "-1";
return 0;
}
ans += (v[point]+con[i].first);
point--;
}
}
for(int i=point;i>=0;i--){
ans+=(v[i]+con[m-1].first);
}
cout << ans;
return 0;
}
C번 Bronze Lilypad Pond (6229, S2)
풀이
BFS 문제이다. m1, m2가 주어지고 이는 말이 움직일 때 세로 m1, 가로 m2만큼 움직인다.
무조건 도달이 가능하다고 문제에서 주어졌기에 나머지는 구현만 하면 끝난다.
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
using namespace std;
int dx[4]={-1,-1,1,1};
int dy[4]={-1,1,-1,1};
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c;
int n, m, t;
cin >> n >> m >> a >> b;
vector<vector<int>> v(n, vector<int>(m));
vector<vector<int>> check(n, vector<int>(m, 0));
int s_x, s_y;
int f_x, f_y;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin >> v[i][j];
if(v[i][j]==3){
s_x=i;
s_y=j;
}
if(v[i][j]==4){
f_x=i;
f_y=j;
}
}
}
int cnt=0;
queue <pair<int, int>> q;
function <void()> bfs=[&](){
pair<int, int> p;
while(!q.empty()){
p=q.front();
int x = p.first;
int y = p.second;
q.pop();
for(int i=0;i<4;i++){
if(x+dx[i]*a >= 0 && x+dx[i]*a < n && y+dy[i]*b >= 0 && y+dy[i]*b < m && check[x+dx[i]*a][y+dy[i]*b]==0 && (v[x+dx[i]*a][y+dy[i]*b]==1 || v[x+dx[i]*a][y+dy[i]*b]==4)){
q.push({x+dx[i]*a, y+dy[i]*b});
check[x+dx[i]*a][y+dy[i]*b] = check[x][y]+1;
}
}
for(int i=0;i<4;i++){
if(x+dx[i]*b >= 0 && x+dx[i]*b < n && y+dy[i]*a >= 0 && y+dy[i]*a < m && check[x+dx[i]*b][y+dy[i]*a]==0 && (v[x+dx[i]*b][y+dy[i]*a]==1 || v[x+dx[i]*b][y+dy[i]*a]==4)){
q.push({x+dx[i]*b, y+dy[i]*a});
check[x+dx[i]*b][y+dy[i]*a] = check[x][y]+1;
}
}
if(check[f_x][f_y]!=0)break;
}
};
q.push({s_x, s_y});
check[s_x][s_y]=1;
bfs();
cout << check[f_x][f_y]-1;
return 0;
}
D번 Decimal Representation (9490, S1)
풀이
맞힌 사람이 20명밖에 없는 무서운 S1 문제이다.
영어 문제기도 하고.. 어떻게 풀어야할지 몰라서 멍청하게 하드 코딩으로 일단 냈다.
머리가 나빠도 손이 조금 고생하면 풀 수 있는 문제였다.
1
2
3
4
5
4/2 = 2
1/4 = 0.25
10/3 = 3.(3)
1/7 = 0.(142857)
1/45 = 0.0(2)
1/N을 이렇게 표현할 때 n을 입력받아서 1~n까지 가장 긴 길이를 출력하면 된다.
예를들어 7은 0.(142857)로 10이고, 8은 0.125니까 5글자이므로 7일 때가 더 크니 여전히 10이다.
https://oeis.org/A051626/b051626.txt
이 링크를 통해 값을 하나하나 보며 조건문으로 풀었다.
1
2
3
4
5
6
7
8
v[383]=386;
v[389]=392;
v[419]=422;
v[433]=436;
v[461]=464;
v[487]=490;
v[491]=494;
v[499]=502;
이런 식으로..
풀고나서 다른 사람은 어떻게 풀었나 보는데 일일히 다 하면서 순환소수 자리가 몇인지 구해줬다.
직접 구현하는게 문제였던거네요. 이게 S1 문제는 아닌 것 같은데..
지금 생각해보니 최대가 500자 정도이므로 소수점 1200까지 구한 다음 같아지는 부분을 찾는 것도
방법이어겠다 싶네요. 수학 문제를 풀다보면 정수론을 공부해야 도움이 되겠다 싶어요.
다른 사람들 코드보면 이미 계산 했던 정보를 이용해서 잘 구현을 했다.
E번 패스 (25559, G4)
풀이
패스
링크에 있습니다.
F번 UDP 스택 (31719, G4)
풀이
스택이 3개가 있고 한 번에 하나만 비울 수 있다.
스택에 쌓인 값을 비울 때 한번에 비워지며 들어간 순서대로 추가된다.
1~N까지 순서가 바뀌어 주어질 때 스택들을 거쳐 만든 배열이 오름차순으로 할 수 있는지 확인한다
아이디어는 간단한게 1개는 무조건 열려있으므로 스택은 2개만 필요하다.
1부터 찾기 시작해서 찾는 값이 나오면 열려있는 스택을 통해 바로 추가를 해주고, 아니면 스택에 넣는다.
입력된 수가 찾는 값이 아닌데, 다른 스택의 뒷부분이 그 수의 -1이라면 그 스택에 입력된 수를 넣으면 된다.
찾는 값이 스택의 맨 앞부분이면 그 스택을 비워주고 찾는 값을 업데이트한다. (코드에서는 0,0으로 초기화) 만약 스택이 꽉찼는데, 넣을 수 없는 값이 들어오면 오름차순으로 정렬을 할 수 없는 경우이다.
이 아이디어는 금방 했는데, 스택에 넣을 때 조건문의 순서가 틀려서 자꾸 WA를 받았다.
값이 있는 스택에 넣을 수 있는지를 확인하고, 비어있는 것에 넣었어야 했는데 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
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
using namespace std;
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long a, b, c;
int n, m, t;
int total=0;
cin >> t;
while(t-->0){
cin >> n;
vector<int>v(n);
for(int i=0;i<n;i++){
cin >> v[i];
}
int chk = 1;
int com=1;
pair<int, int> st1 = {0,0}; //스택1
pair<int, int> st2 = {0,0}; //스택2
for(int i=0;i<n;i++){
if(com==v[i]){
com++;
}
else{
if(st1.second == v[i]-1){
st1.second = v[i];
}
else if(st2.second == v[i]-1){
st2.second = v[i];
}
else if(st1.second==0){
st1.first = v[i];
st1.second = v[i];
}
else if(st2.second==0){
st2.first = v[i];
st2.second = v[i];
}
else {
chk = 0; //불가능
break;
}
}
if(com == st1.first){
com = st1.second+1;
st1.first = st1.second = 0;
}
if(com == st2.first){
com = st2.second+1;
st2.first = st2.second = 0;
}
if(com == st1.first){
com = st1.second+1;
st1.first = st1.second = 0;
}
}
if(chk)cout<<"YES\n";
else cout << "NO\n";
}
return 0;
}
G번 더위 피하기 (15938, G3)
풀이
너무 아쉽게 시간 내에 못 풀었다. 못 푼 이유도 mod 값을 0을 하나 덜 붙여서…
어처구니 없는 실수로 12시간을 고민했다. 그래도 다음에는 안 틀릴거니까..
평소에는 1e9 + 7 이렇게 적는데 무슨 바람이 불어서 100000007 이렇게 했을까?
다음부터는 꼭 지수 표기법을 이용하자.
시작 지점이 주어지고, 도착 지점이 주어진다. 시간도 주어진다.
매초마다 상하좌우 1칸을 움직일 수 있고, 왔던 길도 다시 돌아갈 수 있다.
다만 벽은 못 지나가고, 집에 한 번 도착하면 다시 안 나간다.
시간 내에 집까지 도착하는 경우의 수를 모두 구하면 되는 문제이다.
빡구현 문제다. 3차원 배열 bfs로 하는게 더 좋았겠다 싶긴 하지만 내 코드도 괜찮다.
시간이 200까지 제한이 있어서 배열을 시작 지점과 도착 지점의 위치 조정을 통해서
400x400 배열 안에 넣어줬고, 업데이트 배열을 통해 매번 숫자를 바꿔줬다.
이 때 집에 도착하면 못 나오니까 그것만 신경써주면 되는 구현이었다.
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
using namespace std;
#define mod 1000000007
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; //현재 좌표
cin >> t; //시간
cin >> c >> d; // 집 좌표
cin >> n; // 장애물 개수
//깔끔하게 좌표 조정
c+=(201-a), d+=(201-b);
vector<vector<long long>> dp(403, vector<long long>(403, 0));
for(int i=0;i<n;i++){
cin >> o_1 >> o_2;
o_1 += (201-a), o_2 += (201-b);
if(0<=o_1 && o_1<=402 && 0<= o_2 && o_2 <=402){ //의미 있는 장애물만 남기기
dp[o_1][o_2] = -1; //바로 넣어
}
}
a = 201, b = 201;
if(abs(a-c)+abs(b-d)>t){ //t보다 크면 차피 못감
cout << 0;
return 0;
}
dp[201][201]=1;
int dxx[4] = {0, 0, -1, 1};
int dyy[4] = {-1, 1, 0, 0};
while(t-->0){
vector<vector<long long>> ex(403, vector<long long>(403, 0));
for(int i=1;i<=401;i++){
for(int j=1;j<=401;j++){
if(dp[i][j]==-1)continue; //벽이면 x
else{
for(int kk=0;kk<4;kk++){
if(dp[i+dxx[kk]][j+dyy[kk]]!=-1 && !(i+dxx[kk]==c&&j+dyy[kk]==d)){
ex[i][j] += (dp[i+dxx[kk]][j+dyy[kk]]);
}
}
}
ex[i][j] = ex[i][j]%mod;
}
}
for(int i=1;i<=401;i++){
for(int j=1;j<=401;j++){
if(i==c && j==d)
dp[i][j] += ex[i][j];
else if(dp[i][j]!=-1)
dp[i][j]=ex[i][j];
dp[i][j] = dp[i][j]%mod;
}
}
}
cout << dp[c][d] % mod;
return 0;
}
H번 K-Words Problem (30037, G3)
풀이
문자열을 이용한 순수 구현 문제인데 G3을 받은 골때리는 문제이다.
문제의 조건에 따라 Korea code를 K-Code로, code of Korea도 K-code로 바꾼다.
단어를 하나씩 봐주면서 조건 하나하나를 전부 구현해야했기에 귀찮긴 했다.
특히 문장 부호 조건에서 귀찮아서 대충 처리를 안했더니 문제가 생겨서 안 풀렸다.
결국 하나하나 다 짜서 성공..
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
using namespace std;
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long a, b, c;
int n, m, t;
int total=0;
cin >> n;
vector<vector<string>> v(n);
string s;
for(int i=0;i<n;i++){
while(1){
cin >> s;
v[i].push_back(s);
if(s[s.size()-1]=='.')break;
}
for(int j=1;j<v[i].size()-1;j++){ //2단어 짜리니까
if(v[i][j]=="of"){
if(v[i][j+1] == "Korea" || v[i][j+1] == "Korea." || v[i][j+1] == "Korea?" || v[i][j+1] == "Korea!" || v[i][j+1] == "Korea,"){
int isalpha = 1;
for(int k=0;k<v[i][j-1].size();k++){
if(v[i][j-1][k]=='!' || v[i][j-1][k]=='?' || v[i][j-1][k]==','){ //알파벳인지 확인
isalpha=0;
break;
}
else{
continue;
}
}
if(!isalpha) continue;
else{
v[i][j-1][0] = toupper(v[i][j-1][0]);
v[i][j-1] = "K-" + v[i][j-1];
if(v[i][j+1][v[i][j+1].size()-1]=='!' || v[i][j+1][v[i][j+1].size()-1]=='?' || v[i][j+1][v[i][j+1].size()-1]==',' || v[i][j+1][v[i][j+1].size()-1]=='.'){
v[i][j-1] += v[i][j+1][v[i][j+1].size()-1];
}
v[i].erase(v[i].begin() + j+1);
v[i].erase(v[i].begin() + j);
j--;
}
}
}
}
for(int j=v[i].size()-2;j>=0;j--){ //2단어 짜리니까
if(v[i][j]=="Korea"){
v[i][j+1][0] = toupper(v[i][j+1][0]);
v[i][j+1] = "K-" + v[i][j+1];
v[i].erase(v[i].begin() + j);
j++;
}
}
for(int j=0;j<v[i].size();j++){
cout << v[i][j] << ' ';
}cout << '\n';
}
return 0;
}