구간합을 구하는 간단한 문제였다. 세그먼트 트리 나 누적합 으로 풀면 간단하게 풀린다. 누적합 로직은 다음과 같다.

• (a~b)의 합 = b까지의 합 - (a-1)까지의 합

코드는 두가지 버전으로 작성해보았다.

// 세그먼트 트리 로직
#include <cstdio>

using namespace std;
typedef long long LL;
LL tree[300000];

LL query(int node, int s, int e, int l, int r) {
	if (e < l || r < s) return 0;
	if (l <= s && e <= r) return tree[node];
	else {
		return query(node * 2, s, (s + e) / 2, l, r) + 
			query(node * 2 + 1, (s + e) / 2 + 1, e, l, r);
	}
}
void update(int node, int s, int e, int idx, LL v) {
	if (idx < s || e < idx) return;
	if (s == e) tree[node] = v;
	else {
		update(2 * node, s, (s + e) / 2, idx, v);
		update(2 * node + 1, (s + e) / 2 + 1, e, idx, v);
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
}

int main() {
	int n, m, a, b;
	scanf("%d %d", &n, &m);
	LL input;
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &input);
		update(1, 1, n, i, input);
	}
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &a, &b);
		printf("%lld\n", query(1, 1, n, a, b));
	}
	return 0;
}

// 누적합으로 풀기
#include <cstdio>

using namespace std;
typedef long long LL;

int sum[100001];
int main() {
	int n, m, a, b;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a);
		sum[i] = sum[i - 1] + a;
	}
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &a, &b);
		printf("%d\n", sum[b] - sum[a - 1]);
	}
	return 0;
}

카카오 6번 효율성 에 대해 검색하던 중 찾은 누적합 문제이다. 비슷하게 좌표를 통해 2차원 DP로 푸는 문제이다. 로직은 다음과 같다.

• (i,j) 까지의 누적합 = (i,j)의 값 + (i-1,j)까지의 누적합 + (i,j-1)까지의 누적합 - (i-1,j-1) 까지의 누적합

#define _CRT_SECURE_NO_WARNINGS

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <string.h>
#include <math.h>
#define MAX_NUM 1000000009
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
int arr[1300][1301];


int main() {
	int row, col, a;
	scanf("%d %d", &row, &col);
	for (int i = 1; i <= row; i++) {
		for (int j = 1; j <= col; j++) {
			scanf("%d", &a);
			arr[i][j] = a + arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];
		}
	}

	int n, x1, x2, y1, y2;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		printf("%d\n", arr[x2][y2] - arr[x2][y1-1] - arr[x1-1][y2] + arr[x1-1][y1-1]);
	}
	return 0;
}

약간의 기술이 필요한 투 포인터 문제였다.

일단 기본적으로 5000의 입력값에 1초의 제한시간이기 때문에 O(N^2) 의 복잡도까지는 잘 통과할 것이다. O(N*NlogN) 까지도 가능할거라 생각한다.

여튼 3개의 용액을 골라야 하므로 N의 복잡도는 첫 시작 용액을 고르는 것에, 나머지 N은 투포인터 탐색으로 나머지 2개의 용액을 고르는 것에 사용하여 O(N^2)의 복잡도로 끝마무리 할 수 있다.

로직은 다음과 같다.

• 첫 번째 용액을 순서대로 선택한다.
• 고른 용액 이후의 용액들 중 2개의 용액을 투포인터 탐색을 통해 찾는다.

#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;
typedef long long LL;

LL arr[5001];
int main() {
	LL n;
	scanf("%lld", &n);

	for (LL i = 0; i < n; i++) {
		scanf("%lld", &arr[i]);
	}
	sort(arr, arr + n);
	vector<LL> ans(3);
	LL minn = 21474836470, calc, mid;
	for (LL a = 0; a < n; a++) {
		mid = arr[a];
		for (LL lo = a + 1, hi = n - 1; lo < hi; ) {
			calc = arr[lo] + arr[hi] + arr[a];
			if (abs(calc) <= minn) {
				minn = abs(calc);
				ans[0] = arr[lo];
				ans[1] = arr[hi];
				ans[2] = mid;
			}
			if (calc < 0) {
				lo++;
			}
			else {
				hi--;
			}
		}
	}
	
	sort(ans.begin(), ans.end());
	printf("%lld %lld %lld\n", ans[0], ans[1], ans[2]);
	return 0;
}

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

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;
}