[BOJ] 2022 SISS 2학기 스터디 - 4주차

#5568 : 카드 놓기 (자료구조 Silver 4)

[문제]

 

 

 

[코드 및 결과]

 

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int n, k;
bool check[10];
vector<int> v;
set<int> s;

void solve(int cnt, string str) {
    if (cnt == k) {
        s.insert(stoi(str));
    }
    
    for (int i = 0; i < n; i++) {
        if (check[i] == true) {
            continue;
        }
        check[i] = true;
        
        string result = str;
        result += to_string(v[i]);
        
        solve(cnt + 1, result);
        
        check[i] = false;
    }
}

int main() {
    int num;
    
    cin >> n >> k;
    
    for (int i = 0; i < n; i++) {
        cin >> num;
        v.push_back(num);
    }
    
    solve(0, "");
    
    cout << s.size() << "\n";

    return 0;
}

 

 

 

 

 

 

[설명]

바닥에 놓인 n장의 카드들 중에서 k장을 선택하고, 그 카드들에 적힌 수들을 나열해서 만들 수 있는 수가 몇갠지 알아내는 문제이다.

입력받을 수들을 편하게 넣었다 뺄 수 있게 벡터를 사용하였고, 마지막에 중복 제거 처리를 하기 위해 집합도 사용했다.

 

함수 solve를 만들어서 cnt와 str을 매개변수로 전달하도록 했는데, str에 수들을 추가해주면서 cnt 값을 하나씩 늘려가며 k장을 선택해서 수들을 조합할 수 있게 하려고 했다. 다음은 solve 함수의 내용이다.

 

    if (cnt == k) {
        s.insert(stoi(str));
    }

 

cnt와 k의 값이 같으면 뽑아야할 카드를 다 쓴 것이므로 현재 str에 저장된 문자열을 집합 s에 넣어준다.

 

    for (int i = 0; i < n; i++) {
        if (check[i] == true) {
            continue;
        }
        check[i] = true;
        
        string result = str;
        result += to_string(v[i]);
        
        solve(cnt + 1, result);
        
        check[i] = false;
    }

 

맨 처음에 만든 bool형 배열을 사용해서 사용했는지, 사용하지 않았는지 체크해준다.

상태가 true인 경우, 이미 사용한 카드이므로 넘어가고, false인 경우에는 true로 바꿔준 후에 현재 저장된 문자열 뒤에 그 수를 추가해준다.

그렇게 만들어진 문자열 result를 다시 solve 함수에 매개변수로 넘겨주고 cnt 값은 1 증가시켜서 다음 단계로 진행시킨다. 

이렇게 다 끝낸 후에는 상태를 다시 false로 돌려준다.

 

위의 과정을 거치면 집합 s에 저장된 수들이 있는데, 이 수들의 개수, 즉 집합의 크기를 출력하면 된다.

주의할 점은 수를 조합해서 만들 때 13을 넣어주는 것이나, 1, 3을 차례로 넣어주는 것이나 같은 수가 나오기 때문에 중복이 생길 수 밖에 없다. 집합 set container를 사용하면 자동으로 중복된 값은 지워지기 때문에 이 문제에서 set을 사용한 것이라 보면 된다.

 

 

 

 

#10546 : 배부른 마라토너 (자료구조 Silver 4)

[문제]

 

 

 

[코드 및 결과]

 

#include <iostream>
#include <map>

using namespace std;

int main() {
    int n;
    string name;
    map<string, int> m;
    
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        cin >> name;
        m[name]++;
    }
    
    for (int i = 0; i < n-1; i++) {
        cin >> name;
        m[name]--;
    }
    
    map<string, int>::iterator it;
    for (it = m.begin(); it != m.end(); it++) {
        if (it->second != 0) {
            cout << it->first << "\n";
        }
    }
    
    return 0;
}

 

 

 

 

 

 

[설명]

마라톤에 참여한 n명의 참가자들의 목록과 완주한 n-1명의 참가자들의 목록을 보고 완주하지 못한 1명의 이름을 출력하는 문제이다.

완주한 사람과 완주하지 못한 사람을 쉽게 구분하기 위해 이번에는 map을 사용해보았다.

 

    for (int i = 0; i < n; i++) {
        cin >> name;
        m[name]++;
    }
    
    for (int i = 0; i < n-1; i++) {
        cin >> name;
        m[name]--;
    }

 

윗 부분은 마라톤의 참가한 참가자들의 이름을 입력받으며, 그 이름을 key로 갖는 value 값들에 +1을 해준 것이다.

아랫 부분은 마라톤을 완주한 참가자들의 이름을 입력받으며, 그 이름을 key로 갖는 value 값들에 -1을 해준 것이다.

 

위의 과정을 거치면 마라톤에 참가하고 완주한 사람들의 value값은 0일 것이고, 완주하지 못한 사람의 value값은 1이 된다.

 

    map<string, int>::iterator it;
    for (it = m.begin(); it != m.end(); it++) {
        if (it->second != 0) {
            cout << it->first << "\n";
        }
    }

 

map을 처음부터 끝까지 한번 돌면서 value값이 0이 아닌 것을 찾는 코드이다.

key를 가리키는 건 it->first, value를 가리키는 건 it->second로 보면 된다.

결론적으로 출력해야하는 건 key인 이름이므로 first를 출력해준다.

 

 

 

 

#1476 : 날짜 계산 (자유 Silver 5)

[문제]

 

 

 

[코드 및 결과]

 

#include <iostream>

using namespace std;

int main() {
    int e, s, m;
    int year = 1;
    
    cin >> e >> s >> m;
    
    while (true) {
        if ((year - e) % 15 == 0 && (year - s) % 28 == 0 && (year - m) % 19 == 0) {
            cout << year << "\n";
            break;
        }
        else {
            year++;
        }
    }
    
    return 0;
}

 

 

 

 

 

 

[설명]

E S M을 이용해서 연도를 나타내는 방식이 있는데, 이런 방식으로 표기된 연도를 입력 받으면 원래 우리가 알고 있는 연도로는 가장 빠른 게 몇 년인지 구하는 문제이다.

E는 1~15, S는 1~28, M은 1~19까지의 범위를 가지고 있고, 1 1 1인 경우 1년, 2 2 2인 경우 2년, ..., 1 16 16인 경우 16년이다.

 

아래와 같이 연도를 쭉 나열해서 적으면 다음과 같다. 

 

year	e	year - e	s	year - s	m	year - m
1	1	0	1	0	1	0
2	2	0	2	0	2	0
...	...	...	...	...	...	...
15	15	0	15	0	15	0
16	1	15	16	0	16	0
17	2	15	17	0	17	0
18	3	15	18	0	18	0
19	4	15	19	0	19	0
20	5	15	20	0	1	19
21	6	15	21	0	2	19
...	...	...	...	...	...	...
29	14	15	1	28	10	19
30	15	15	2	28	11	19

 

1로 돌아가는 순간 year - e, year - s, year - m이 각각 15, 28, 19의 배수가 되고 있음을 확인할 수 있는데, 15, 28, 19로 나누었을 때 딱 나누어떨어질 때의 연도가 구해야하는 연도임을 알 수 있다.

이를 이용해서 코드를 짜보기로 했다.

 

일단 E, S, M을 입력받고 while문을 만든다.

 

   while (true) {
        if ((year - e) % 15 == 0 && (year - s) % 28 == 0 && (year - m) % 19 == 0) {
            cout << year << "\n";
            break;
        }
        else {
            year++;
        }
    }

 

year - e, year - s, year - m이 모두 각각 15, 28, 19로 나누어떨어지게 된다면 우리가 원하는 연도가 나오므로 출력하면 된다.

나누어떨어지지 않는 경우, 연도에 +1을 하면서 다시 체크해보도록 한다.