씅의 기록하는 개발노트

문제출처

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

문제풀이

연구소에 이어 조금 예외가 추가된 문제이다. 기본적으로는 완전탐색을 통해 풀면 된다 생각되었다.

소스코드 작성에 앞서 문제 풀이 방법은 다음과 같이 생각해봤다.

1. 활성화할 바이러스를 선택한다(selectVirus)

- 선택한 바이러스가 m개라면 바이러스를 퍼트린다.

2. 바이러스를 퍼뜨릴때 모든 경우를 다 사용해야 하기 때문에 새로운 2차원 배열을 생성한다.

- 활성화할 바이러스를 큐에 담는다.

- 문제에서 제시한 조건을 따라 벽이거나 이미 바이러스가 전파된 경우를 제외하고 바이러스를 전파한다.

3. 활성화된 바이러스로 퍼지는데 걸리는 시간을 구한다.

- 이때 입력으로 받은 map이 빈칸이고 새로운 timeMap이 초기 값이라면 바이러스가 완전히 퍼지지 않은것으로 판단한다.

- 활성화된 바이러스는 제외해야하기 때문에 map이 0인 것만 카운팅한다.

4. 이후 return 받은 결과값이 최대값과 같다면 바이러스를 모든 빈 칸에 전파할 수 없는 경우이므로 -1을 출력하고 이외의 경우 최소값을 출력한다.

생각보다 시간이 많이 걸렸다. 처음 90%대에서 자꾸 틀렸습니다가 나왔는데 활성화된 바이러스를 제외하지 않아서 였다. 백준 게시판의 반례모음집을 보고 어디서 잘못됬는지 파악할 수 있었다.

소스 작성전에 예외없이 알고리즘을 짤 수 있도록 습관을 더 길러야겠다.

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
// 2020/04/12 14:55 문제풀이 시작 -> 16:40 문제풀이 완료
struct VIRUS {
    int y, x;
};
bool isAllSpread;
int n, m, ans=987654321;
int dy[] = {0, 0, 1, -1};
int dx[] = {1, -1, 0, 0};
int map[50][50];
vector<VIRUS> virus, selected;
void init() {
    cin>>n>>m;
    for (int y=0; y<n; y++) {
        for (int x=0; x<n; x++) {
            cin>>map[y][x];
            if (map[y][x] == 2) virus.push_back({y,x});
        }
    }
}
int spreadVirus() {
    isAllSpread = 1;
    queue<VIRUS> q;
    int timeMap[50][50];
    memset(timeMap, -1, sizeof(timeMap));

    for (int i=0; i<selected.size(); i++)  {
        q.push(selected[i]);
        timeMap[selected[i].y][selected[i].x] = 0;
    }

    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        q.pop();

        for (int i=0; i<4; i++) {
            int ny=y+dy[i];
            int nx=x+dx[i];

            // out of bound
            if (ny<0 || nx<0 || ny>=n || nx>=n) continue;

            // 벽 or 이미 바이러스 퍼진 경우
            if (map[ny][nx] == 1 || timeMap[ny][nx] != -1) continue;

            q.push({ny, nx});
            timeMap[ny][nx] = timeMap[y][x] + 1;
        }
    }

    int time=0;
    for (int y=0; y<n; y++) {
        for (int x=0; x<n; x++) {

            // 전부 전파하지 못한 경우
            if (map[y][x] == 0 && timeMap[y][x] == -1) {
                isAllSpread=0;
                return 987654321;
            }
            // 활성화 하지 않은 바이러스는 제외
            else if (map[y][x] == 0) {
                time = max(time, timeMap[y][x]);
            }
        }
    }
    return time;
}
void selectVirus(int index) {
    if (selected.size() == m) {
        int time = spreadVirus();
        if (isAllSpread) ans = min(ans, time);

        return;
    }

    for (int i=index; i<virus.size(); i++) {
        selected.push_back(virus[i]);
        selectVirus(i+1);
        selected.pop_back();
    }
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    init();
    selectVirus(0);
    if (ans == 987654321) cout<<"-1"<<"\n";
    else cout<<ans<<"\n";
    return 0;
}

문제출처

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

문제풀이

 재귀함수를 이용한 완전탐색 문제입니다. n의 최대값이 11이므로 완전탐색이 가능하다고 판단되어 완전탐색으로 풀이하였습니다.

숫자 순서는 변하지 않고 연산자 우선순위도 적용되지 않기 때문에 현재까지 계산한 값과 연산자를 통한 계산을 해주면 되는 문제입니다. 처음에 최대값, 최소값을 0xfffffff으로 초기화 했는데 틀렸습니다가 나왔다. 문제를 잘 읽어보면 최댓값과 최솟값이 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 라는 문구를 보아 10억으로 초기화 해서 해결했습니다.

 저같은 실수를 하신 분들을 위해 반례 하나 적어두겠습니다.

5

100 100 100 100 10

0 0 4 0

소스코드

#include <iostream>
using namespace std;
int n, mx=-1000000000, mn=1000000000;
int a[100], oper[4];

void solve(int curSum, int depth) {
    if (depth == n) {
        mx = curSum > mx ? curSum : mx;
        mn = curSum > mn ? mn : curSum;
        return;
    }

    if (oper[0] > 0) {
        oper[0]--;
        solve(curSum + a[depth], depth+1);
        oper[0]++;
    }
    if (oper[1] > 0) {
        oper[1]--;
        solve(curSum - a[depth], depth+1);
        oper[1]++;
    }
    if (oper[2] > 0) {
        oper[2]--;
        solve(curSum * a[depth], depth+1);
        oper[2]++;
    }
    if (oper[3] > 0) {
        oper[3]--;
        solve(curSum / a[depth], depth+1);
        oper[3]++;
    }
}

void init() {
    cin>>n;
    for (int i=0; i<n; i++) cin>>a[i];
    for (int i=0; i<4; i++) cin>>oper[i];
    solve(a[0], 1);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    init();
    cout<<mx<<"\n"<<mn<<"\n";
    return 0;
}

문제 출처

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

문제 풀이

문자열을 확인하면서 "("인 경우 stack에 push

만약 문자열이 ")"이고 stack이 비어있다면 VPS가 아니라고 판단.

stack이 비어있지 않다면 top에 "("인지 확인한뒤 pop

모든 문자열을 확인한 뒤 stack이 비어있다면 VPS 비어있지 않으면 VPS가 아니라고 판단할 수 있다.

이 문제는 stack이 아닌 카운팅하면서 문제를 풀 수도 있으며 두가지 방법 모두 O(N)의 복잡도를 가진다.

소스 코드

//
//  main.cpp
//  BOJ_9012
//
//  Created by sw on 18/12/2019.
//  Copyright © 2019 seungwoo. All rights reserved.
//

#include <iostream>
#include <stack>

using namespace std;
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    cin>>t;
    
    while (t--) {
        string input;
        cin>>input;
        stack<char> st;
        
        for (int i=0; i<input.size(); i++) {
            if (input[i] == '(') {
                st.push(input[i]);
            } else {
                if (!st.empty() && st.top() == '(') {
                    st.pop();
                } else {
                    st.push(')');
                    break;
                }
            }
    }
        if (st.empty()) cout<<"YES"<<"\n";
        else cout<<"NO"<<"\n";
    }
        
    return 0;
}