#7 기본 수학1 - 2

백준 문제풀이

 

10250번 문제 : ACM 호텔

문제 :

 

소스코드 :

#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int t;
    int h, w, n;
    int result; 
    cin >> t;

    for(int i=0; i<t; i++) {
        cin >> h >> w >> n;
        // 맨위층 
        if (n % h == 0) {
            result = n / h;
            result += h * 100;
            cout << result << "\n";
        }
        // n / h 에서 +1 하면 오른쪽 이동 (1씩 더함) 
        // n % h 만큼 위로 이동 (100씩 더함) 
        else {
            result = n / h + 1;
            result += (n % h) * 100;
            cout << result << "\n";
        }
    }
    
    return 0;
}

 

 

 

2775번 문제 : 부녀회장이 될테야

문제 :

 

소스코드 :

#include <iostream>

using namespace std;

int func(int h, int w) {
    if (h == 0) {
        return w;
    }
    if (w == 1) {
        return 1;
    }
    // k층의 n호 = k-1층의 n호 + k층의 n-1호
    return (func(h-1,w) + func(h,w-1));
} 


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    // k 층의 n 호에 살려면 k-1층(아래층)의 1호부터 n호까지의 합만큼
    // 사람들 데려와 살아야 함 
    // 아파트는 0층부터 있고, 각층에는 1호부터, 0층의 i호에는 i명이 산다.
    // 1 5 15 35
    // 1 4 10 20
    // 1 3 6 10
    // 1 2 3 4
    
    // k층의 n호 = k-1층의 1호부터 n호까지의 합 = k-1층의 n호 + k층의 n-1호
    // 따라서 재귀함수를 이용하면 거주민 수를 구할 수 있다. 
    int t;
    int k, n;
    cin >> t;
    for(int i=0; i<t; i++) {
        cin >> k >> n;
        cout << func(k,n) << "\n";
    } 
    
    return 0;
}

 

삼중 for문으로 작성한 사람들도 많았다. 뭐가 더 좋은지는 잘 모르겠다.

 

삼중 for문의 시간 복잡도는 O(n의 3승)

2번씩 호출하는 재귀함수의 시간 복잡도는 O(2의 n승)

 

음.. 확실한건 재귀함수가 직관성이 훨씬 좋은 것 같다.

 

 

10757번 문제 : A + B

문제 :

 

소스코드 :

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    string a, b;
    int t;
    vector<int> v;
    cin >> a >> b;
    
    // a와 b 맨 앞에 "0" 넣기 
    a.insert(0, "0");
    b.insert(0, "0");
    
    // string a와 b의 길이 맞추기 , ex) 0524 02811 -> 00524 02811
    int aLen = a.length();
    int bLen = b.length();
    if (aLen > bLen) {
        for(int i=0; i<(aLen - bLen); i++) {
            b.insert(0, "0");
        }
    }
    else if (bLen > aLen) {
        for(int i=0; i<(bLen - aLen); i++) {
            a.insert(0, "0");
        }
    }
    
    // a+b를 더한 값을 넣어줄 벡터 길이 맞추기 
    aLen = a.length();
    v.assign(aLen, 0); // 00000
    
    // 00524 + 02811
    for (int i=v.size()-1; i>0; i--) {
        t = (a[i]-'0') + (b[i]-'0') + v[i];
        if (t >= 10) {
            v[i] = t - 10;
            v[i-1] = 1;
        }
        else v[i] = t;
    }

    // 03335와 같이 맨 앞 자리가 0인 경우 삭제
    if (v[0] == 0) v.erase(v.begin() + 0);
    
    for(int i=0; i<v.size(); i++) {
        cout << v[i];
    }
    
    return 0;
}

 

 

 

 

 

문제들 출처 :

https://www.acmicpc.net/step/8

기본 수학 1 단계