전형적인 투포인터 문제이다.

10만의 입력값에 1초의 시간 제한을 보자마자 최소 O(NlogN)의 복잡도를 사용해야 한다는 것을 생각해야 한다. 또한 정렬이 되어있다는 조건을 본 후 이분탐색 또는 투포인터탐색을 떠올린 뒤 로직을 생각하면 된다.

이 문제의 경우 간단한 로직을 사용한다.

• lo, hi 를 양끝으로 잡은 뒤 값을 비교하며 투 포인터 탐색을 진행한다.
• 진행 시 계산한 값이 음수이면서 0에 가까운지 양수이면서 0에 가까운지 체크한다.
• 각 경우에 따라 lo를 증가시킬지 hi를 감소시킬지 정해주며 답을 찾아가면 된다.

#define _CRT_SECURE_NO_WARNINGS

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <string.h>
#include <math.h>

using namespace std;
int arr[100001];
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

	vector<int> ans(2);
	int minn = 2147483647, calc;
	
	for (int lo = 0, hi = n-1; lo < hi; ) {
		calc = arr[lo] + arr[hi];
		if (calc < 0) {
			if (abs(calc) <= minn) {
				minn = abs(calc);
				ans[0] = arr[lo];
				ans[1] = arr[hi];
				lo++;
			}
			else {
				lo++;
			}
		}
		else {
			if (abs(calc) <= minn) {
				minn = abs(calc);
				ans[0] = arr[lo];
				ans[1] = arr[hi];
				hi--;
			}
			else {
				hi--;
			}
		}
	}
	sort(ans.begin(), ans.end());
	printf("%d %d\n", ans[0], ans[1]);
	return 0;
}

그래프 + dp 문제 이다.

이 문제를 풀기 이전에 dp와 dfs 를 같이 사용해서 생각하는 방법을 기를 수 있어야 한다. 일단 해당 문제는 top-down dp 방식으로 풀이할 수 있다.

예를 들어 7 부터 tree 를 순회한다고 할 때,

• 7번째 마을을 우수마을로 선정하는 경우
• 7번째 마을을 우수마을로 선정하지 않는 경우

2가지의 경우로 DP 상태를 선정할 수 있다. 또한 7번째 마을을 우수마을로 선정하기 위해서는 7번째 마을과 연결된 마을들이 선정되지 않는 경우를 알아야 하고, 7번째 마을을 우수마을로 선정하지 않기 위해서는 상관이 없다.

이를 이용해서 dp 로직을 구할 수 있다.

• 특정 마을이 선정되는 경우 = (자식 마을이 선정되지 않은 경우의 합) + 특정 마을의 인원수
• 특정 마을이 선정되지 않는 경우 = (자식 마을의 두 경우의 최대값의 합)

이를 dfs 로 구현하기 위해서는 재귀 느낌의 방식으로 잘 짜임새있게 코딩해야 한다.

즉, 맨 마지막 leaf 노드는 (자기 자신의 인원수, 0) 를 반환한다는 방향성을 가지고 쭉 탐색해주어야 한다. 그 부분이 다음의 dfs 함수 코드이다. (말이 이상하지만 패스..)

void dfs(int x, vector<vector<int>> &v) {
    for (int i = 0; i < v[x].size(); i++) {
        int nx = v[x][i];
        if (check[nx]) continue;
        check[nx] = 1;
        dfs(nx, v);
        dp[x][0] += dp[nx][1];
        dp[x][1] += max(dp[nx][0], dp[nx][1]);
    }
    dp[x][0] += arr[x];
    return;
}

#define _CRT_SECURE_NO_WARNINGS

#include <string>
#include <vector>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <queue>
#include <stack>

#define MAX_INT 1000000000
using namespace std;

typedef pair<int, int> pii;
int arr[10001];
int check[10001];
int dp[10001][2];

void dfs(int x, vector<vector<int>> &v) {
    for (int i = 0; i < v[x].size(); i++) {
        int nx = v[x][i];
        if (check[nx]) continue;
        check[nx] = 1;
        dfs(nx, v);
        dp[x][0] += dp[nx][1];
        dp[x][1] += max(dp[nx][0], dp[nx][1]);
    }
    dp[x][0] += arr[x];
    return;
}
int main() {
    int n;
    cin >> n; 
    vector<vector<int>> v(n+1);

    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
    }
    int a, b;
    for (int i = 1; i < n; i++) {
        scanf("%d %d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    check[1] = 1;
    dfs(1, v);

    printf("%d", max(dp[1][0], dp[1][1]));
    return 0;
}

좀 단순한 dfs 탐색 문제였다.

각 크기의 색종이의 개수를 배열에 저장해둔 다음, 해당 위치 부터 차례대로 5, 4, 3, 2, 1 크기의 색종이를 대조하고, 다음 노드를 탐색하는 로직만 구현하면 된다. 

전체 배열의 크기가 10*10 로 크지 않으며, 색종이의 종류 역시 5개이므로 시간 제한은 매우 널널하다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#include <string.h>
#include <map>

#define INF 100000000

using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;
typedef long long LL;
int arr[11][11];
int check[11][11];
vector<pii> one;
int card[] = { 0,5,5,5,5,5 };
int cnt;

bool queryPaper(int k, int tx, int ty) {
    for (int x = 0; x < k; x++) {
        for (int y = 0; y < k; y++) {
            int cx = tx + x;
            int cy = ty + y;
            if (arr[cx][cy] != 1 || check[cx][cy] == 1) return false;
        }
    }
    return true;
}
void checkPaper(int k, int tx, int ty) {
    for (int x = 0; x < k; x++) {
        for (int y = 0; y < k; y++) {
            int cx = tx + x;
            int cy = ty + y;
            check[cx][cy] = 1;
        }
    }
}

void uncheckPaper(int k, int tx, int ty) {
    for (int x = 0; x < k; x++) {
        for (int y = 0; y < k; y++) {
            int cx = tx + x;
            int cy = ty + y;
            check[cx][cy] = 0;
        }
    }
}

int res = 1000;
void dfs(int z, int c) {
    if (z >= (int)one.size()) {
        res = min(c, res);
        return;
    }
    int tx = one[z].first;
    int ty = one[z].second;
    if (check[tx][ty] == 1) dfs(z + 1, c);
    else {
        for (int k = 5; k >= 1; k--) {
            if (queryPaper(k, tx, ty)) {
                if (card[k] == 0) continue;
                else {
                    card[k] -= 1;
                    checkPaper(k, tx, ty);
                    dfs(z + 1, c + 1);
                    card[k] += 1;
                    uncheckPaper(k, tx, ty);
                }
            }
        }
    }
    
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    for (int i = 1; i <= 10; i++) {
        for (int j = 1; j <= 10; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 1) one.push_back({ i,j });
        }
    }

    if (one.empty()) cout << 0;
    else {
        dfs(0, 0);
        if (res == 1000) cout << -1;
        else cout << res;
    }
    return 0;
}

간단한 탐색 문제이다. 바로 로직을 보면 다음과 같다.

• 입력받은 문자열을 알파벳 순으로 정렬해준다.
• map 을 두어 이미 체크한 문자열을 탐색하지 않도록 설정해준다.
• 그 후 문자열의 idx 에 대해 check 해주며 브루트 포스 탐색을 실시한다.

이러면 그냥 답이 나온다... 간단~

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#include <string.h>
#include <map>

#define INF 100000000

using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

int arr[100001];
int check[100001];
int visit[100001];
int n, t;

void dfs(string x, string cur, map<string, int> &m) {
    if (cur.size() == x.size()) {
        cout << cur << "\n";
        return;
    }
    for (int i = 0; i < x.size(); i++) {
        string cx = cur + x.at(i);
        if (check[i] == 0 && m[cx] == 0) {
            m[cx] = 1;
            check[i] = 1;
            dfs(x, cx, m);;
            check[i] = 0;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    string input;
    cin >> n;
    for (int i = 0; i < n; i++) {
        memset(check, 0, sizeof(check));
        cin >> input;
        map<string, int> m;
        sort(input.begin(), input.end());
        dfs(input, "", m);
    }


    return 0;
}

트릭이 필요한 탐색 문제였다.

일단 기존 DFS 를 사용해서 단순하게 check 하며 탐색한다. 이 때 cycle 이 생기는 경우 해당 cycle 에 포함되지 않는 노드의 개수를 구하기 때문에 visit 배열을 하나 더 만든다. 그 후 다음과 같은 규칙을 세운다.

• check는 color 로 칠하되 다른 컬러의 check 를 만났다면 그건 이미 만들어진 cycle 이므로 해당 color 구축시에는 cycle 노드 개수가 0이다. (0 return)
• check 가 0으로 되어있어 순회하는 경우 visit 배열에 몇 개의 노드를 탐색 중인지 메모해놓는다.
• check 가 color 로 칠해져있는 노드에 다시 한번 더 접근한 경우 해당 color 단계에서 cycle 이 발생했다는 것이다. 이 때 visit 에 저장되어있는 탐색 노드 개수를 전체 cnt 탐색 수에서 빼주게 되면 cycle 노드의 개수가 된다.
• 즉, dfs 의 결과값을 전체 노드의 개수에서 차근차근 빼주면 cycle 에 속하지 않는 노드의 개수가 만들어진다.

말이 좀 어려운데 기본적으로 color dfs 처럼 check 배열 순회 탐색을 진행한다. 거기에다가 visit 배열 하나만 추가해주어서 몇개의 노드를 탐색 중인 건지를 저장해 cycle 을 만드는 노드의 개수를 확인할 수 있게만 해주면 끝난다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#include <string.h>

#define INF 100000000

using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

int arr[100001];
int check[100001];
int visit[100001];
int n, t;

int dfs(int x, int color, int cnt) {
    int next = arr[x];
    if (check[next]) {
        if (check[next] == color) {
            return cnt - visit[next];
        }
        else return 0;
    }
    else if (!check[next]) {
        check[next] = color;
        visit[next] = cnt;
        return dfs(next, color, cnt+1);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n;
        memset(check, 0, sizeof(check));
        for (int j = 1, input ; j <= n; j++) {
            cin >> arr[j];
        }
        int res = n;
        for (int j = 1, color = 1; j <= n; j++) {
            if (check[j] == 0) {
                check[j] = color;
                visit[j] = 0;
                res -= dfs(j, color++, 1);
            }
        }

        cout << res << endl;
    }



    return 0;
}

시간 제한은 1초에 테스크 케이스의 개수가 1000개이니 각 테스트 케이스마다 최소 10만 이내의 복잡도로 끝내야 하는 문제이다. 이때 수가 20000까지의 수이기 때문에 반복문 2개를 놓는순간 제한에 걸리게 된다.

이 문제는 조건과 나머지의 규칙을 통해 풀 수 있다. 다음 식들을 쭉보자

• 10 = (1 * 7) + 3
• 100 = (10 * 7) + 30
• 101 = (10 * 7) + 31
• ......

이 식들을 보았을 때 나누게 되는 수가 10곱만큼 늘어나게 되면 나머지 역시 10곱만큼 늘어나게 된다. 또한 나누게 되는 수가 1만큼 늘어나게 되면 나머지 역시 1만큼 늘어나게 된다. 이를 이용해서 string, int 값을 queue 에 넣어가면서 나머지가 0이 될 때까지 탐색을 돌릴 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#include <string.h>

#define INF 100000000

using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

int check[20001];

string bfs(int n) {
    queue<pair<string,int>> q;
    q.push({ "1", 1 });
    // 첫번째 나머지
    check[1] = 1;

    while (!q.empty()) {
        string cstr = q.front().first;
        int cnum = q.front().second;
        q.pop();
        if (cnum == 0) return cstr;
        for (int i = 0; i < 2; i++) {
            // i=0 : 10을 곱한다
            // i=1 : 10을 곱한 뒤 1을 더한다.
            int tx = (cnum * 10 + i) % n;
            if (check[tx]) continue;
            check[tx] = 1;
            q.push({ cstr + to_string(i), tx });
        }
    }
    return "";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int t;
    cin >> t;
    // 100 101 110 111 
    int n;
    for (int i = 0; i < t; i++) {
        memset(check, 0, sizeof(check));
        cin >> n;
        // 각 테케마다 10만의 복잡도 안으로 끝내야 한다.
        string ans = bfs(n);
        if (ans.empty()) cout << "BRAK" << "\n";
        else cout << ans << "\n";
    }

    return 0;
}

약간의 테크닉이 필요한 탐색 문제였다.

예전에 바이러스 관련해서 비슷한 문제를 푼거 같긴한데 로직은 다음과 같다.

1. 불 위치에서 BFS 탐색을 시작해 번지는 시간대를 check 배열에 메모
2. 메모된 check 배열에 따라 지훈이의 위치에서 탐색을 시작
3. 양 모서리 지점까지 도달했으면 탈출한 것으로 체크

딱 봤을 때는 간단한데 1번과 2번을 연동시키는게 좀 생각하기 어렵다. 허나 여러번 풀어보면 간단해보이니 계속 풀어대자

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#include <string.h>

#define INF 100000000

using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

char arr[1001][1001];
int check[1001][1001];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
int h, w, sx, sy, fx, fy;
int n, m;

// 불의 위치에서 탐색
void fire_bfs(int x, int y) {
    queue<tiii> q;
    q.push({ x, y, 0 });
    check[x][y] = 0;

    while (!q.empty()) {
        tiii cur = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int cx = get<0>(cur) + dx[i];
            int cy = get<1>(cur) + dy[i];

            if (cx < 1 || cx > n || cy < 1 || cy > n) continue;
            if (arr[cx][cy] == '#') continue;
            if (check[cx][cy] != -1 && check[cx][cy] <= get<2>(cur) + 1) continue;
            // 이미 불이 번진 상태이면 건너뛴다.

            check[cx][cy] = get<2>(cur) + 1;
            q.push({ cx, cy, check[cx][cy] });
        }
    }
}
// 지훈이의 위치에서 탐색
int go_bfs(int x, int y) {
    queue<tiii> q;
    q.push({ x, y, 0 });
    int answer = INF;
    while (!q.empty()) {
        tiii cur = q.front();
        int cur_x = get<0>(cur);
        int cur_y = get<1>(cur);
        int cur_tm = get<2>(cur);
        q.pop();

        if (cur_x == 1 || cur_x == n || cur_y == 1 || cur_y == m) {
            answer = min(answer, cur_tm + 1);
            continue;
        }
        for (int i = 0; i < 4; i++) {
            int cx = get<0>(cur) + dx[i];
            int cy = get<1>(cur) + dy[i];

            if (cx < 1 || cx > n || cy < 1 || cy > m) continue;
            if (arr[cx][cy] != '.') continue;
            if (check[cx][cy] != -1 && check[cx][cy] <= get<2>(cur) + 1) continue;
            // 불이 이미 번져있는 곳이면 갈 수 없다.

            check[cx][cy] = get<2>(cur) + 1;
            q.push({ cx, cy, get<2>(cur) + 1 });
        }
    }
    return answer;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> m;
    string tp;
    vector<pii> fire;
    pii now;

    for (int i = 1; i <= n; i++) {
        cin >> tp;
        for (int j = 1; j <= m; j++) {
            arr[i][j] = tp.at(j - 1);
            if (arr[i][j] == 'F') {
                fire.push_back({ i,j });
            }
            else if (arr[i][j] == 'J') {
                now = { i,j };
            }
        }
    }

    memset(check, -1, sizeof(check));
    for (auto pi : fire)
        fire_bfs(pi.first, pi.second);

    int ans = go_bfs(now.first, now.second);
    if (ans == INF) cout << "IMPOSSIBLE";
    else cout << ans;


    return 0;
}

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

단순한 탐색 문제였다.

직사각형의 범위에 벽이 있나없나만 체크하며 queue 에 넣어주면서 탐색을 진행하면 풀리는 단순한 문제였다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <string.h>

#define INF 100000000

using namespace std;
typedef pair<int, int> pii;
struct Square {
    int x, y;
    int tm;
};

Square initSquare(int _x, int _y, int _tm) {
    Square tp;
    tp.x = _x;
    tp.y = _y;
    tp.tm = _tm;
    return tp;
}

int arr[1001][1001];
int check[1001][1001];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
int h, w, sx, sy, fx, fy;
int n, m;

bool checkSquare(int x, int y) {
    if (x < 1 || x > n || y < 1 || y > m) return false;
    if (y + w - 1 > m || x + h - 1 > n) return false;
    
    for (int i = x; i < x + h; i++) {
        if (arr[i][y] == 1) return false;
        if (arr[i][y + w - 1] == 1) return false;
    }

    for (int i = y; i < y + w; i++) {
        if (arr[x][i] == 1) return false;
        if (arr[x + h - 1][i] == 1) return false;
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }
    cin >> h >> w >> sx >> sy >> fx >> fy;

    queue<Square> q;
    q.push(initSquare(sx, sy, 0));
    int answer = INF;
    while (!q.empty()) {
        Square tp = q.front();
        q.pop();

        if (tp.x == fx && tp.y == fy) {
            answer = min(answer, tp.tm);
            continue;
        }
        for (int i = 0; i < 4; i++) {
            int cx = tp.x + dx[i];
            int cy = tp.y + dy[i];
            if (check[cx][cy] == 1) continue;
						// 직사각형의 범위에 벽이 있는지 체크하는 checkSquare
            if (!checkSquare(cx, cy)) continue;

            check[cx][cy] = 1;
            q.push(initSquare(cx, cy, tp.tm + 1));
        }
    }

    if (answer == INF) cout << -1;
    else cout << answer;

    return 0;
}

전형적인 BFS 문제이다.

단순히 길만 따라서 check 배열에 메모 후 탐색, 메모 후 탐색 의 로직으로 문제를 풀게 되면 틀리게 된다. 탐색하는 경우의 수가 사실 2배 더 많기 때문이다.

칼이 있는지, 없는지에 대한 경우를 생각해야 하기 때문에 2배이다. 예를 들어 (2,3) 위치에 이동할 때, 칼을 가진 상태로 이동하는 것과 칼을 가지지 않은 상태로 이동하는 것은 명백히 다른 경우의 수이다. 떄문에 이 두 가지 경우를 다르게 봐야하고 그에 따라 check배열 또한 3차원 배열로 만들어주어야 한다. 그 후에는 다음 코드와 같이 단순히 BFS 탐색을 때리면 끝!

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <string.h>

#define INF 10000000

using namespace std;
typedef pair<int, int> pii;

struct Move {
    int x, y, tm;
    bool sword;
};
Move initMove(int _x, int _y, int _tm, bool _s) {
    Move m;
    m.x = _x;
    m.y = _y;
    m.tm = _tm;
    m.sword = _s;
    return m;
}

int arr[101][101];
int check[101][101][2];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m, t;
    cin >> n >> m >> t;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }

    queue<Move> q;
    q.push(initMove(1, 1, 0, false));
    check[0][0][0] = 1;
    int min_time = INF;

    while (!q.empty()) {
        Move cur = q.front();
        q.pop();
        if (cur.tm > t) continue;
        if (cur.x == n && cur.y == m) {
            min_time = min(min_time, cur.tm);
            continue;
        }

        for (int i = 0; i < 4; i++) {
            int cx = cur.x + dx[i];
            int cy = cur.y + dy[i];
            if (cx < 1 || cx > n || cy < 1 || cy > m) continue;
            
            if (cur.sword == false) { // 1. 아직 칼을 못찾은 경우
                if (check[cx][cy][0]) continue;
                if (arr[cx][cy] == 1) {
                    continue;
                }
                else if (arr[cx][cy] == 2) { // 1.1. 칼을 찾은 경우
                    check[cx][cy][0] = 1;
                    q.push(initMove(cx, cy, cur.tm + 1, true));
                }
                else if (arr[cx][cy] == 0) { // 1.2. 그냥 길인 경우
                    check[cx][cy][0] = 1;
                    q.push(initMove(cx, cy, cur.tm + 1, false));
                }
            }
            else if (cur.sword == true) { // 2. 칼을 찾은 경우
                if (check[cx][cy][1]) continue;
                check[cx][cy][1] = 1;
                q.push(initMove(cx, cy, cur.tm + 1, true));
            }
        }

    }
    if (min_time == INF)
        cout << "Fail";
    else
        cout << min_time;

    return 0;
}