[1일 1백준] 1주차 복습하기. (14650 ~ 14659)

 오늘은 조금 신기한 날이다. 파이썬가지고 컴퓨터공학개론에서 서로 코드를 비교해서 보고서를 올리는게 과제였는데... 이젠 내가 자의로 그런 일을 진행하게 되다니 기분이 묘하다. 선배님이 올려주신 백준의 문제들은 이전 선린고에서 출제된 문제라고 한다. 나도 처음에는 디미고나 선린고 같은데 가는게 꿈이었는데, 이번 기회에 기분은 맛볼 수 있을 듯하다. 잡설은 건너뛰고 바로 본론으로 들어가보자.

 

D번 H번 I번은 풀지 못했다... 아직... 물론 선배님이 답은 올려 주셨지만 어떻게 해야할지...?

---

A + B번 :

https://www.acmicpc.net/problem/14650 & https://www.acmicpc.net/problem/14651

14650번: 걷다보니 신천역 삼 (Small)

14651번: 걷다보니 신천역 삼 (Large)

내 코드 (A):

#include<iostream>

using namespace std;

int counter = 0;

//sum until now, depth left to explore.
void rescursive(int sum, int depth){
    if(!depth){
        if(!(sum % 3))
            counter += 1;
        return;
    }
    rescursive(sum + 0, depth - 1);
    rescursive(sum + 1, depth - 1);
    rescursive(sum + 2, depth - 1);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    
    rescursive(1, n - 1);
    rescursive(2, n - 1);

    cout << counter;

    return 0;
}

 문제를 보자마자, "모든 자릿수를 더해서 3으로 나누어지면 3의 배수"라는 사실은 너무 유명해서 당연히 써먹어야겠다 싶었다. 그 사실을 이용해서 경우의 수를 딱! 구해주는 수학식을 고민하다가 n의 상한이 겨우 9라는 점에서 3^9 = 19,638번의 연산만 진행하면 되기 때문에, 일일이 계산해도 괜찮겠다 싶어 저렇게 재귀로 풀어보았다.

내 코드 (B):

#include<iostream>
#include<cstring>

#define MOD 1000000009

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    if(n == 1){
        cout << "0\n";
        return 0;
    }
    
    long sum = 2;
    n -= 2;
    while(n--){
        sum = (sum % MOD * 3) % MOD;
    }

    cout << sum;

    return 0;
}

 이 문제의 n 상한은 33,333이었기 때문에, 3^33,333개의 숫자들을 일일이 체크할 수는 없는 것은 당연했다. 그래서 dp로 풀어보면 되지 않을까 싶어서 3개의 int를 담는 dp1[3]과 dp2[3]를 만들고,

dp2[i] = (다음 자릿수에서 Sum(모든 자릿수) % 3 = i 인 숫자의 개수)

dp1[i] = (현재 자릿수에서 Sum(모든 자릿수) % 3 = i 인 숫자의 개수)

로 정의했다. 이 정보를 알고 있으면 dp1[i]에 0,1,2를 더해 생기는 (Sum(모든 자릿수) + 이번 자릿수) % 3 즉, 다음 i값이 무엇인지를 알아내서 해당하는 dp2[i]에 더해주면 되는 것이었다. (그래서 dp2는 매번 비워주고, dp1과 dp2를 swap해주어야 한다. 아님 그냥 dp[33333][3]짜리 이차원 배열도 good.)

 

 다만 여기까지 생각이 미치고 나니까, 처음 dp1 = {0,1,1}일 때를 제외하고는 차례대로 dp1[0], dp[1], dp[2] 를 더해주는 효과가 생겨서 dp2 = {2,2,2}가 되고, 앞으로 계속~ 이 값에 3이 곱해질 뿐 변하지 않는다는 것을 알았다. 그래서 n = 1을 제외한 나머지 값들은 단순히 2에 3을 곱해주고 그게 MOD보다 크다면 나머지 연산을 하기만 하면 된다는 것을 알았다. 그래서 long변수 하나를 선언해서 값을 출력하게 놔누었더니 맞았다.

 

선배님의 한마디 : 재귀를 사용해도 된다는 걸 코드 보고 깨달았습니다 덕분에 배워갑니다 딱히 할 말은 없는데 Large에서 long 자료형을 굳이 사용한 이유가 있는지? 궁금합니다

 

O_O long을 굳이 이용할 필요가 없었다...

 

Slack에 달 답변 :  Large에서 long을 이용했던게 MOD가 10의 자릿수가 넘어길래 혹시 int범위를 넘어서 dp가 커질 가능성이 있는 것은 아닐까 싶어서 이용했습니다. 필요가 없는 작업이었군요...

---

C번 :

https://www.acmicpc.net/problem/14652

14652번: 나는 행복합니다~

내 코드 :

#include<iostream>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long n, m, k;
    cin >> n >> m >> k;

    cout << (k / m) << ' ' << (k % m);

    return 0;
}

 이전에도 풀어본 나머지 문제였다. 브론즈 5문제는 다풀어봐서 쉬울 것으로 생각해서 방심했다가 한번 거꾸로 생각하는 바람에 틀리고 그 다음에 맞춰서 제출... ㅠㅠ 덜렁거리는 성격은 어디 안가는 건가 제발 떠나라 제발

 

선배님의 한마디 : 간단한 문제 = PASS

---

D번 :

https://www.acmicpc.net/problem/14653

14653번: 너의 이름은

내 코드 :

#include<iostream>
#include<vector>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    bool checked_message[26] = {true,};
    vector<pair<int, char>> messages;
    int people, msg_count, msg_answer;

    cin >> people >> msg_count >> msg_answer;
    msg_answer--;

    for(int i = 1; i <= msg_count; i++){
        pair<int, char> input;
        cin >> input.first >> input.second;
        messages.emplace_back(input);
    }

    if(messages[msg_answer].first == 0){
        cout << "-1\n";
        return 0;
    }

    for(int i = msg_count; i >= msg_answer || messages[msg_answer].first == messages[i].first; --i){
        checked_message[(int)(messages[i].second - 'A')] = true;
    }
    
    for(int i = 0; i < people; i++){
        if(!checked_message[i])
            cout << (char)(i + 'A') << ' ';
    }

    return 0;
}

(개인적으로 너무 어려워서 포기해버린...)

 몇번 틀리고 선배님의 코드를 보고 나서야 어느 정도 제대로 된 알고리즘을 알아낼 수 있었다. 내가 구현했던 알고리즘은 이것이 아니라 각 사람별로 언제 마지막으로 로그오프 했는지를 그 때마다 업데이트하고 저장해서 푸는 방법이었는데, 그러다가 코드가 꼬여서 엄청 많이 틀렸다. 결국 선배님의 알고리즘을 이용한 끝에야 맞을 수 있었다. 지금 생각해보니 그런 일이 왜 발생했는지 이유를 알 것 같은데, 출력해야하는 것은 "메세지를 보지 않은" 사람들이고 내가 알아 낼 수 있는 것은 "메세지를 본" 사람들일텐데, 이걸 생각 못하고 계속 무식하게 한 코드에 우겨 넣으려고 하다보니까 이렇게 된게 아닐 까 싶다. 선배님이 "애드혹이라 능지가 필요한"문제라고 코멘트 했는데, 뭔 소린지 모르겠어서 따로 서핑해야할 것 같다.

---

E번 :

https://www.acmicpc.net/problem/14654

14654번: 스테판 쿼리

내 코드 :

#include<iostream>
#include<vector>

using namespace std;

bool is_winner(int a, int b){
    if(a == 1 && b == 2)
        return true;
    if(a == 2 && b == 3)
        return true;
    if(a == 3 && b == 1)
        return true;
    return false;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, max = 1, curr = 1;
    bool is_last_winner_1;
    int rsp1[300] = {0,}, rsp2[300] = {0,};
    cin >> n;
    
    for(int i = 0; i < n; i++){
        int input;
        cin >> input;
        rsp1[i] = input;
    }
    for(int i = 0; i < n; i++){
        int input;
        cin >> input;
        rsp2[i] = input;
    }

    is_last_winner_1 = is_winner(rsp1[0], rsp2[0]);
    for(int i = 1; i < n; i++){
        if(rsp1[i] == rsp2[i]){
            is_last_winner_1 = !is_last_winner_1;
            curr = 1;
        } else {
            if(is_winner(rsp1[i], rsp2[i]) == is_last_winner_1){ // winner strike!
                curr++;
                max = (curr > max ? curr : max);
            } else { // winner change.
                is_last_winner_1 = !is_last_winner_1;
                curr = 1;
            }
        }
    }

    cout << max;

    return 0;
}

비기는 게임이 없다보니(문제의 조건에서 비기는 경우 전에 이겼던 사람이 폭사된다고 했으므로...), 의외로 전에 이겼던 사람이 계속 이기는 경우만 보면 되서 그렇게 어렵지 않았다. 어렵지는 않았는데, 선배님이 무슨 지적을 해주실지... 기대된다.

 

선배님의 한마디 : rsp에 바로 cin 하면 더 좋을 거 같습니다

Aㅏ... 생각해보니 이 배열 vector가 아니었다. -펑-

---

F번 :

https://www.acmicpc.net/problem/14655

14655번: 욱제는 도박쟁이야!!

내 고등어 :

#include<iostream>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, max = 0;
    cin >> n;

    if(n == 2){
        int a, b;
        cin >> a >> b;
        max += (a + b) > -1 * (a + b) ? (a + b) : -1 * (a + b);
        cin >> a >> b;
        max += (a + b) > -1 * (a + b) ? (a + b) : -1 * (a + b);
    } else {
        for(int i = 0; i < 2 * n; i++){
            int input;
            cin >> input;
            max += abs(input);
        }
    }

    cout << max;

    return 0;
}

이 문제의 핵심은 "컨트롤"에 있다고 보았다. 동전을 뒤집을 수 있는 횟수는 무한대이므로. "n개의 동전이 있을 때 k번째 (1<=k<=n) 동전만을 뒤집는 것이 모든 n에 대해서 가능하다" 라고 한다면, 실질적으로 동전을 뒤집는 과정을 생각할 필요 없이 그냥 모든 동전을 양수/음수로 바꿔버리면 되는 부분이다. 하지만 나의 저 추측은 n = 2일때는 성립하기 않았기 때문에 (한 동전만 뒤집기가 불가능) 그 경우를 대비한 코드를 따로 짜놓고 냈는데 맞았다. 아마 나머지 경우에 대해서는 내 추측이 맞아 들어갔나보다. 처음에는 추측을 증명해보려고 별짓을 다 했는데 실패했다. 아무래도 수학공부가 정말 부족한듯...

---

G번 :

https://www.acmicpc.net/problem/14656

14656번: 조교는 새디스트야!!

내 콛으 :

#include<iostream>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, counter = 0;
    cin >> n;

    for(int i = 1; i <= n; i++){
        int input;
        cin >> input;
        if(i != input)
            counter++;
    }

    cout << counter;

    return 0;
}

내 한마디도 : 간단한 문제 = PASS

---

J번 :

https://www.acmicpc.net/problem/14659

14659번: 한조서열정리하고옴ㅋㅋ

내 코드 ;;

#include<iostream>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, counter = 0, curr_height = -1, max = 0;
    cin >> n;

    for(int i = 0; i < n; i++){
        int input;
        cin >> input;
        if(input > curr_height){
            curr_height = input;
            counter = 0;
        } else {
            counter++;
        }
        max = (counter > max ? counter : max);
    }

    cout << max;

    return 0;
}

이 녀석도 스테판 쿼리 문제랑 비슷하게 greedy하게 풀면 된다. 중복되는 봉우리의 높이가 없으므로 연산자 걱정은 좀 덜었다.

 

우선 이렇게 올려보자.

1. D / H / I 해결

2. 선배 코드랑 비교해보기.