[BOJ] 단계별로 풀어보기 - 기본 수학 1

지난 겨울방학때 풀고 개강 후 손을 놨던 백준을 다시 풀기로 마음먹었다.

너무 오랜만이라 뇌가 안돌아갈 것 같아서 적당히 뇌를 깨울 수 있는 기본 수학1을 풀어보았다.

파이썬과 C++ 둘다 짜는 것을 연습하고 있지만 수학 문제는 두 언어에서 구현이 다를 것 같지 않아 C++로만 짰다.

마지막 문제 빼고는 코딩적으로 얻어가는 건 없었지만 상당히 재밌었기에 한번에 몰아서 포스팅한다.

 

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

1712번: 손익분기점

#include <iostream>
using namespace std;

int main(){
    int a, b, c;
    long long n;
    cin >> a >> b >> c;

    if(b >= c){
        printf("-1");
    }
    else{
        n = a / (c - b) + 1;
        printf("%lld", n);
    }
}

처음엔 시간 제한을 보지 못하고 반복문으로 짰다가 시간초과에 걸렸다.
그냥 식을 잘세우면 된다.

 

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

2292번: 벌집

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;

    if(n == 1){
        cout << 1;
        return 0;
    }

    if(n >= 2 && n <= 7){
        cout << 2;
        return 0;
    }

    int cnt = 2;
    int sum = 1;
    for(int i = 1;; i++){
        sum += 6 * i;
        if(n > sum){
            cnt++;
        }
        else{
            cout << cnt;
            break;
        }
    }
}

한 번에 갈 수 있는 수들의 개수, 두 번에 갈 수 있는 수들의 개수 등을 세서 규칙을 찾을 수 있었다.

 

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

1193번: 분수찾기

#include <iostream>
using namespace std;

int main(){
    int x;
    cin >> x;

    if(x == 1){
        cout << 1 << "/" << 1;
        return 0;
    }

    int n = 1;
    int i = 2;
    while(1){
        int a, b;
        int max = n + i;
        if(x <= max){
            int diff = max - x;
            if(i % 2 == 1){
                a = 1 + diff;
                b = i - diff;
            }
            else{
                a = i - diff;
                b = 1 + diff;
            }

            cout << a << "/" << b;
            break;
        }
        n = max;
        i++;
    }
}

홀수 번째 대각선 숫자들의 특징, 짝수 번째 대각선 숫자들의 특징을 파악하는 것이 핵심이다.

그 다음 x번째 수가 몇 번째 대각선에 존재하고 그 안에서 몇 번째 숫자인지 알아내면 풀 수 있다.

 

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

2869번: 달팽이는 올라가고 싶다

 

#include <iostream>
#include <cmath>
using namespace std;

int main(){
    int a, b, v;
    int cnt = 1;
    cin >> a >> b >> v;

    if(a == v){
        cout << cnt;
        return 0;
    }
    
    if((v-a) % (a-b) == 0){
        cnt += (v-a) / (a-b);
        cout << cnt;
    }

    else{
        cnt += (v-a) / (a-b) + 1;
        cout << cnt;
    }
    
}

정상에 도달하면 다시 미끄러지지 않기 때문에 결국 v-a까지 걸리는 시간을 구하는 것이 핵심이다.

 v-a까지 걸리는 시간에 대한 식을 세우면 (v-a) / (a+b)가 되는데 (v-a) % (a-b)가 0이 아니라면 이동거리가 모자라므로 1을 추가로 더해주어야한다.

 

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

10250번: ACM 호텔

#include <iostream>
using namespace std;

int main(){
    int t, h, w, n;
    int floor, num;
    cin >> t;

    for(int i = 0; i < t; i++){
        cin >> h >> w >> n;

        if(n % h == 0){
            floor = h;
            num = n / h;
        }
        else{
            floor = n % h;
            num = n / h + 1;
        }

        if(num < 10){
            cout << floor << "0" << num << "\n";
        }
        else{
            cout << floor << num << "\n";
        }
    }
}

조건을 해석하면 결국 위쪽으로 가는 순서로 방이 채워지는 것을 알 수 있다. 따라서 n번째 채워지는 방의 층, 번호를 구하는 식을 찾는 것은 쉬웠는데 n % h가 0인 경우가 특이 케이스였는데 이것을 놓쳐서 약간 해맸었다.

 

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

2775번: 부녀회장이 될테야

#include <iostream>
using namespace std;

int main(){
    int t, a, n;
    cin >> t;
    for(int i = 0; i < t; i++){
        cin >> a;
        cin >> n;

        int arr[15][15] = {0,};
        for(int j = 0; j < 15; j++){
            for(int k = 1; k < 15; k++){
                if(j == 0){
                    arr[j][k] = k;
                }
                else{
                    arr[j][k] = arr[j - 1][k] + arr[j][k - 1];
                }
            }
        }
        cout << arr[a][n] << "\n";
    }
}

2차원배열을 초기화 시켜서 DP를 사용해 한번에 풀었다. 문제에서 k가 0열이 아닌 1열부터 시작해서 0열을 모두 0으로 초기화 해준다음에 점화식을 적용해서 index error를 피할 수 있었다.

 

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

2839번: 설탕 배달

#include <iostream>
using namespace std;

int main(){
    int n, cnt = 0;
    cin >> n;

    if(n % 5 == 0){
        cout << n / 5;
        return 0;
    }
    while(n > 0){
        n -= 3;
        cnt++;
        if(n % 5 == 0){
            cout << cnt + n / 5;
            return 0;
        }
    }
    cout << "-1";
}

뭔가 예전에 풀 때 많이 본 그리디 문제였다. 5kg 봉지를 최대한 많이 사용해야하므로 5kg으로 나누어떨어질때까지 3kg 봉지를 사용해나가면 풀 수 있다.

 

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

10757번: 큰 수 A+B

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main(){
    string a, b;
    cin >> a >> b;

    int len_a = a.length();
    int len_b = b.length();

    if(len_a > len_b){
        for(;len_b < len_a; len_b++){
            b = "0" + b;
        }
    }
    else{
        for(;len_a < len_b; len_a++){
            a = "0" + a;
        }
    }

    vector <int> ans;

    int idx = len_b - 1;
    int carry = 0;
    for(;idx >= 0; idx--){
        int num_a = a[idx] - '0';
        int num_b = b[idx] - '0';

        ans.push_back((num_a + num_b + carry) % 10);
        carry = (num_a + num_b + carry) / 10;
    }
    if(carry > 0)
        ans.push_back(carry);
    for(int i = ans.size() - 1; i >= 0; i--){
        cout << ans[i];
    }
}

난이도가 브론즈5이길래 그냥 long long형 쓰면 될 줄 알았지만 어림도 없었다.
string 클래스를 이용해 입력받고 자리수를 맞춰준다음에 뒷자리부터 덧셈을 진행하여 vector에 저장해나갔다. 계산과정에서 carry를 생각하는 것이 중요했다. 

 

파이썬으로는 그냥 a + b만 하면 풀리는 문제라 큰 수를 다룰 때 왜 파이썬을 쓰는지 몸소 체감할 수 있었다.
C++ 이틀 차로써 vector도 처음 써봐서 좀 재밌는 문제였다.

---