[스터디] 문제 풀이 - 2주차

브 - 11034, 17224
실 - 1049, 1543, 1449, 1080
골 - 12904

---

11034번

문제

세 캥거루 사이의 거리 중 가장 먼 것을 선택 / 입력이 없을 때 프로그램을 종료하는 것이 중요(EOF 처리)

파이썬 풀이

def main():
    a, b, c = map(int, input().split())

    answer = max(abs(a-b)-1, abs(b-c)-1)
    print(answer)

if __name__ == "__main__":
    while True:
        try:
            main()
        except:
            break

C++ 풀이

#include <iostream>

using namespace std;

int main(){
    int a, b, c, answer;

    while(scanf("%d %d %d", &a, &b, &c) != EOF){
        answer = max(abs(a-b)-1, abs(b-c)-1);
        printf("%d\n", answer);
    }
}

C++ EOF 처리 방법
1. if(cin.eof()) break;
2. scanf() != EOF

17224번

문제

어려운 문제 난이도 기준으로 낮은 것부터 풀어나가다가 막히면 쉬운 문제 난이도 기준으로 풀 수 있는 것을 풀어야하므로 정렬 2번 필요

파이썬 풀이

n, l, k = map(int, input().split())

problem = [list(map(int, input().split())) for _ in range(n)]
problem = sorted(problem, key=lambda x: x[1])
score = 0
i = 0

while i < k:
    if problem[i][1] <= l:
        score += 140
        i += 1
    else:
        break
problem = sorted(problem, key=lambda x: x[0])
while i < k:
    if problem[i][0] <= l:
        score += 100
    i += 1

# for i in range(k):
#     if problem[i][1] <= l:
#         score += 140
#     else:
#         problem = sorted(problem, key=lambda x: x[0])
#         if problem[i][0] <= l:
#             score += 100

print(score)

C++ 풀이

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

using namespace std;

bool cmp0(const pair<int, int> &a, const pair<int, int> &b){
    return a.first < b.first;
}

bool cmp1(const pair<int, int> &a, const pair<int, int> &b){
    return a.second < b.second;
}

int main(){
    int n, l, k;
    vector<pair<int, int>> problem;

    scanf("%d %d %d", &n, &l, &k);

    for(int i = 0; i < n; ++i){
        int e, h;
        scanf("%d %d", &e, &h);
        problem.push_back(make_pair(e, h));
    }
    sort(problem.begin(), problem.end(), cmp1);

    int i = 0;
    int score = 0;
    while(i < k){
        if(problem[i].second <= l){
            score += 140;
            ++i;
        }
        else break;
    }
    sort(problem.begin(), problem.end(), cmp0);
    while(i<k){
        if(problem[i].first <= l) score += 100;
        ++i;
    }

    printf("%d", score);
}

정렬 짱나,,
함수를 2개나 만들어야 한다.

---

1049번

문제

다 낱개로 구매하는 경우, 패키지와 낱개를 섞어서 구매하는 경우, 다 패키지로 구매하는 경우 총 3개의 가격을 구해 최솟값 찾기

파이썬 풀이

n, m = map(int, input().split())

price = [list(map(int, input().split())) for _ in range(m)]

pack_min = min(price, key=lambda x: x[0])[0]
each_min = min(price, key=lambda x: x[1])[1]

# 다 낱개, 패키지+낱개, 다 패키지
answer = min(each_min*n, pack_min*(n//6)+each_min*(n%6), pack_min*(n//6+1))
print(answer)

C++ 풀이

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

using namespace std;

int main(){
    int n, m, pack_min, each_min, answer;
    vector<int> package;
    vector<int> each;

    cin >> n >> m;
    
    for(int i = 0; i < m; ++i){
        int p, e;
        cin >> p >> e;
        package.push_back(p);
        each.push_back(e);
    }

    pack_min = *min_element(package.begin(), package.end());
    each_min = *min_element(each.begin(), each.end());

    answer = min({each_min*n, pack_min*(n/6)+each_min*(n%6), pack_min*(n/6+1)});
    cout << answer;
}

*<algorithm> 헤더의 min_element를 사용하여 vector와 같은 컨테이너의 최솟값의 인덱스를, *을 붙여 그 값을 얻을 수 있다.

1543번

문제

단어의 개수를 앞에서부터 체크

파이썬 풀이

doc = input()
word = input()

answer = doc.count(word)
    
print(answer)

파이썬에는 count( )라는 좋은 기능이 있다.

C++ 풀이

#include <iostream>
#include <string>

using namespace std;

int main(){
    string doc;
    string word;
    getline(cin, doc);
    getline(cin, word);

    int word_len, answer = 0, i = 0;
    string::size_type n;

    word_len = word.length();

    while(i < doc.length()){
        n = doc.find(word, i);
        if(n!= string::npos){
            ++answer;
            i = n + word_len;
        }
        else break;
    }

    cout << answer;
}

공백 포함 문자열을 입력할 땐 getline 이용하기!!!
string에서 find(찾을 문자열, 시작 위치)를 이용하면 찾는 문자열의 시작 위치를 반환한다.
찾는 문자가 없을 경우에는 npos를 리턴

1449번

문제

앞쪽 위치부터 고쳐나가는데 이미 테이프가 붙은 부분은 지나가기

파이썬 풀이

n, l = map(int, input().split())

leak = list(map(int, input().split()))
leak.sort()
fix = [False for _ in range(2001)]
answer = 0

for i in leak:
    if fix[i] is False:
        answer += 1
        for j in range(i, i+l):
            fix[j] = True
        
print(answer)

C++ 풀이

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

using namespace std;

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

    vector<int> leak;
    vector<int> fix(2001);

    int t, answer = 0;

    for(int i = 0; i < n; ++i){
        cin >> t;
        leak.push_back(t);
    }
    sort(leak.begin(), leak.end());
    for(auto i:leak){
        if(fix[i] == 0){
            ++answer;
            for(int j = i; j < i+l; ++j){
                fix[j] = 1;
            }
        }
    }
    cout << answer;
}

굳이 fix라는 배열을 사용하지 않아도 충분히 풀 수 있을 것 같은데 생각대로 잘 안된다...
똑같은 논리로 접근하는데 단순 변수로만 처리하려니 계속 오류남.. ㅜㅜ

1080번

문제

A행렬과 B 행렬 사이에 다른 부분이 발견되면 일단 뒤집기

파이썬 풀이

n, m = map(int, input().split())

A = [list(map(int, input())) for _ in range(n)]
B = [list(map(int, input())) for _ in range(n)]

answer = 0

def flip(arr, x, y):
    for i in range(x, x+3):
        for j in range(y, y+3):
            arr[i][j] = 1 - arr[i][j]


if n < 3 or m < 3:
    if A == B:
        print(answer)
    else:
        print(-1)
else:
    for i in range(n - 2):
        for j in range(m - 2):
            if A[i][j] != B[i][j]:
                flip(A, i, j)
                answer += 1

    if A == B:
        print(answer)
    else:
        print(-1)

어떤 기준으로 뒤집을 3*3을 정해야할지 몰라서 일단 A와 B가 다른 부분이 나오면 뒤집어주었다.
3*3 크기이므로 전체 행렬 크기에서 -2 범위까지만 뒤집을 수 있다.

C++ 풀이

#include <iostream>
#include <vector>

using namespace std;

int n, m;

void flip(vector<vector<int>> &arr, int x, int y){
    for(int i = x; i < x+3; ++i){
        for(int j = y; j < y+3; ++j){
            arr[i][j] = !arr[i][j];
        }
    }
}

bool check(vector<vector<int>> arr1, vector<vector<int>> arr2){
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(arr1[i][j] != arr2[i][j]) return false;
        }
    }
    return true;
}

int main(){
    int answer = 0;
    char temp;
    cin >> n >> m;

    vector<vector<int>> A(n, vector<int>(m));
    vector<vector<int>> B(n, vector<int>(m));

    // A 행렬 입력
    for(int i = 0; i < n; ++i){
        for (int j = 0; j < m; ++j){
            cin >> temp;
            A[i][j] = bool(temp - '0');
        }
    }
    // B 행렬 입력
    for(int i = 0; i < n; ++i){
        for (int j = 0; j < m; ++j){
            cin >> temp;
            B[i][j] = bool(temp - '0');
        }
    }
 
    // 행렬 검사
    if(n < 3 || m < 3){
        if(check(A, B)) cout << answer << endl;
        else cout << -1 << endl;
    }
    else{
        for(int i = 0; i < n-2; ++i){
            for (int j = 0; j < m-2; ++j){
                if(A[i][j] != B[i][j]){
                    flip(A, i, j);
                    ++answer;
                }
            }
        }
        if(check(A, B)) cout << answer << endl;
        else cout << -1 << endl;
    }
}

이게.. 맞나...?
너무 비효율적으로 푼 것 같다

---

12904번

문제

문제에서 주어진 조건을 거꾸로 대입해서 입력값이 나오는지 찾기

파이썬 풀이

s = input()
t = input()

while len(t) > len(s):
    if t[-1] == 'A':
        t = t[:-1]
    else:
        t = t[:-1]
        t = t[::-1]

if s == t:
    print(1)
else:
    print(0)

C++ 풀이

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

using namespace std;

int main(){
    string s;
    string t;

    cin >> s;
    cin >> t;

    while(t.length() > s.length()){
        if(t.back() == 'A'){
            t.pop_back();
        }
        else{
            t.pop_back();
            reverse(t.begin(), t.end());
        }
    }

    if(s == t)  cout << 1 << endl;
    else    cout << 0 << endl;
}

string 헤더를 사용하면 문자열을 더 간단하게 다룰 수 있다.