DP 에 비트마스킹까지 포함시킨 문제이다.

일단 수를 일일이 다 확인해가면서 0부터 9까지 있는지 확인하는 작업은 복잡도 측면에서 몇십배 정도 더 늘어나게 된다. 때문에 이를 위해 비트마스킹 기법을 통한 체킹 로직이 필요하다.

추가로 DP 메모라이징 기법을 통해 이 문제를 비교적 간단하게 풀 수 있다. 처음에만 봤을 때 어렵지 한 번 이해하면 다음에는 쉽지(??!) 않을까 생각하는 문제이다.

다음에 한 번 더 풀어보는 걸로..

#define _CRT_SECURE_NO_WARNINGS

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

using namespace std;
typedef pair<int, string> pii;
typedef long long LL;

int N;
int check[10][101][1 << 10];

int stair(int start, int length, int number) {
    if (length == N) 
        return (number == (1 << 10) - 1) ? 1 : 0;
    
    int &result = check[start][length][number];
    if (result != -1)
        return result;

    result = 0;
    if (start - 1 >= 0)
        result += stair(start - 1, length + 1, number | 1 << (start - 1));
    if (start + 1 < 10)
        result += stair(start + 1, length + 1, number | 1 << (start + 1));
    result %= 1000000000;
    return result;
}
int main() {
    cin >> N;

    int res = 0;
    for (int i = 1; i <= 9; i++) {
        memset(check, -1, sizeof(check));
        res += stair(i, 1, 1 << i);
        res %= 1000000000;
    }
    cout << res << endl;

    
    return 0;
}

구현 + DFS 문제였다.

네트워크 개수를 세는 듯한 문제인데 입력받은 U, D, L, R 에 따라 쭉~ 이어주는 동시에 다음 값이 현재 있는 값으로 들어올수도 있는지 확인하는 로직을 구현하면 간단한 문제였다. 다시 로직을 정리하면 다음과 같다.

• 지도 (0,0) 부터 check 되어있지 않으면 dfs 로 해당 지점으로부터 연결되어있는 모든 지도지점을 check
• SAFE ZONE 개수 한개 추가
• 그 후 check 안되어있는 지점으로부터 dfs 처리해서 똑같이 네트워크 check
• SAFE ZONE 한개 추가

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
typedef pair<int, string> pii;
char arr[1001][1001];
int check[1001][1001];
int dx[] = { -1,0,1,0 }; // 위, 왼쪽, 아래, 오른쪽
int dy[] = { 0,-1,0,1 };
int n, m;
char dz[] = { 'D', 'R', 'U','L' };

bool dfs_check(int a, int b, int i) {
    return (a<1 || a > n || b < 1 || b > m) || dz[i] != arr[a][b] || check[a][b] == 1;
}
void dfs(int x, int y) {
    switch (arr[x][y]) {
    case 'D':
        if (x + 1 <= n && check[x + 1][y] == 0) 
            check[x + 1][y] = 1, dfs(x + 1, y);
        for (int i = 0; i < 4; i++) {
            if (i == 2) continue;
            int cx = x + dx[i];
            int cy = y + dy[i];
            if (dfs_check(cx, cy, i)) continue;
            check[cx][cy] = 1, dfs(cx, cy);
        }
        break;
    case 'L':
        if (y - 1 >= 1 && check[x][y-1] == 0) 
            check[x][y - 1] = 1, dfs(x, y - 1);
        for (int i = 0; i < 4; i++) {
            if (i == 1) continue;
            int cx = x + dx[i];
            int cy = y + dy[i];
            if (dfs_check(cx, cy, i)) continue;
            check[cx][cy] = 1,  dfs(cx, cy);
        }
        break;
    case 'R':
        if (y + 1 <= m && check[x][y + 1] == 0) 
            check[x][y + 1] = 1, dfs(x, y + 1);
        for (int i = 0; i < 4; i++) {
            if (i == 3) continue;
            int cx = x + dx[i];
            int cy = y + dy[i];
            if (dfs_check(cx, cy, i)) continue;
            check[cx][cy] = 1, dfs(cx, cy);
        }
        break;
    case 'U':
        if (x - 1 >= 1 && check[x - 1][y] == 0) 
            check[x - 1][y] = 1, dfs(x - 1, y);
        for (int i = 0; i < 4; i++) {
            if (i == 0) continue;
            int cx = x + dx[i];
            int cy = y + dy[i];
            if (dfs_check(cx, cy, i)) continue;
            check[cx][cy] = 1, dfs(cx, cy);
        }
        break;
    }
    return;
}
int main() {
    scanf("%d %d", &n, &m);

    string input;
    for (int i = 1; i <= n; i++) {
        cin >> input;
        for (int j = 1; j <= m; j++) {
            arr[i][j] = input.at(j-1);
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (check[i][j] == 1) continue;
            check[i][j] = 1;
            dfs(i, j);
            res += 1;
        }
    }

    printf("%d", res);
    return 0;
}

단순 BFS 를 사용하면 100만 + 300만 정도의 복잡도가 나오게 되어서 전혀 복잡도가 터질 일이 없다.

따라서 BFS 를 따라 로직만 잘 처리해주면 된다. 로직은 다음과 같다.

• 처음 입력된 수와 비어있는 문자열을 queue 에 넣는다.
• 이 후 queue 의 front 를 빼고 3가지 연산 각각을 할 수 잇는지 확인하고 연산이 가능하면 연산된 값을 다시 queue 에 넣고 해당 숫자를 더한 문자열또한 queue 에 넣는다.
• 위의 과정을 1이 나올 떄까지 반복한다.

생각보다 간단한 알고리즘이다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
typedef pair<int, string> pii;
int check[2000001];


void split_str(string s, vector<string>& ans) {
    auto current = s.find(',');
    auto previous = 0;
    while (current != string::npos) {
        string substring = s.substr(previous, current - previous);
        if (substring != "")
            ans.push_back(substring);
        previous = current + 1;
        current = s.find(',', previous);
    }
    ans.push_back(s.substr(previous, current - previous));
    cout << ans.size() - 1 << endl;
    for (auto i : ans)
        cout << i << " ";
    return;
}
int main() {
    int n;
    cin >> n;

    queue<pii> q;
    q.push({ n,"" });

    int cx;
    string ct;
    vector<string> ans;
    ans.push_back(to_string(n));

    if (n == 1) {
        cout << 0 << endl;
        cout << 1;
        return 0;
    }

    while (!q.empty()) {
        cx = q.front().first;
        ct = q.front().second;
        q.pop();
        if (cx == 1) {
            split_str(ct, ans);
            break;
        }
        if (cx % 3 == 0 && check[cx / 3] == 0) {
            check[cx / 3] = 1;
            q.push({ cx / 3, ct + "," + to_string(cx / 3) });
        }
        if (cx % 2 == 0 && check[cx / 2] == 0) {
            check[cx / 2] = 1;
            q.push({ cx / 2, ct + "," + to_string(cx / 2) });
        }
        if (check[cx - 1] == 0) {
            q.push({ cx - 1 , ct + "," + to_string(cx - 1) });
        }
    }

    return 0;
}

생각보다 간단한 문제였다.

N번째 큰 수를 찾아야하므로 크기가 N 초과가 되면 안되는 우선순위 큐를 선언한 다음에 하나씩 입력받다가 N 초과가 되는 경우 제일 작은 값을 뺴주어 N개를 유지시키는 식으로 쭉 입력받고 맨 마지막에 우선순위 큐에 있는 N개의 수 중에서 제일 작은 값이 N번째 큰 수가 된다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>

using namespace std;
priority_queue<int, vector<int>, greater<int>> pq;
int main()
{
    int n, input;
    scanf("%d", &n);
    for (int i = 0; i < n * n; i++) {
        scanf("%d", &input);
        pq.push(input);
        if (pq.size() > n) {
            pq.pop();
        }
    }

    printf("%d", pq.top());
    
    return 0;
}

단순 탐색 문제인것 같다.

문자와 정수 pair 를 저장하는 vector 를 만든다. 그 후 문자열의 값을 하나씩 확인하면서 문자를 vector 에 넣되, 넣을 때 비교할 폭탄 문자열과 확인하여 같은 값이라면 몇번재 index 와 같은지를 정수로 같이 넣어준다.

이로써 폭탄이 만일 터지더라도 그 다음에 저장되어있는 정수를 확인해 계속해서 이어지는 문자가 들어올 시 폭탄이 터지도록 로직을 구현할 수 있다.

복잡도는 100만 * 36 + 36n? 정도? 라서 2초에 비해 넉넉한 복잡도를 가질 것이라 생각된다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <iostream>
#include <tuple>
#include <cmath>
#include <stack>

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

int main()
{
    string a, b;
    vector<pii> st;

    cin >> a >> b;
    int cnt = 0;
    for (int i = 0; i < a.size(); i++) {
        if (st.empty() || st.back().second < 0) {
            st.push_back({ a.at(i), (b.at(0) == a.at(i) ? 0 : -1) });
        }
        else {
            if (st.back().second >= 0) {
                if (b.at(st.back().second + 1) == a.at(i)) 
                    st.push_back({ a.at(i), st.back().second + 1 });
                else 
                    st.push_back({ a.at(i), (b.at(0) == a.at(i) ? 0 : -1) });
            }
        }

        if (st.back().second == b.size() - 1) {
            for (int k = 0; k < b.size(); k++)  st.pop_back();
        }
    }
    if (st.empty()) cout << "FRULA\n";
    else {
        for (auto c : st) printf("%c", c);
    }
    

    return 0;
}

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <tuple>
#include <cmath>

using namespace std;
typedef pair<long double, long double> pii;
int n, cnt = 0, a, b;
priority_queue<int, vector<int>, greater<int>> pq;
vector<pii> v;
int main()
{
    int n;
    long double a, b;
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%Lf %Lf", &a, &b);
        v.push_back({ a, b });
    }
    long double x1, y1, x2, y2, x3, y3;
    x1 = v[0].first;
    y1 = v[0].second;
    long double res = 0;
    for (int i = 1; i < v.size(); i++) {
        x2 = v[i - 1].first;
        y2 = v[i - 1].second;
        x3 = v[i].first;
        y3 = v[i].second;
        res += (x1 * y2 + x2 * y3 + x3 * y1) - (x2 * y1 + x3 * y2 + x1 * y3);
    }
    printf("%.1Lf", abs(res/2));
    return 0;
}

수학적 풀이가 필요한 문제이다...

간단한 백트래킹을 사용한 구현 문제이다.

로직은 생각보다 간단하다. dfs 순회를 하면서 넣으려는 숫자가

• 행에 있는지
• 열에 있는지
• 박스에 있는지

3가지만 확인하면 된다. 이 때 각각을 전부 순회를 때리게 되면 각각 9번의 연산이 생기게 된다. 그렇게 되면 81번의 공간에 9개의 숫자를 확인하되 각각 27번의 check 연산을 하게 되어 복잡도에 큰 문제가 생기지 않는다고 판단된다.

허나 좀더 빠르게 연산하기 위해 해쉬를 두어 숫자를 체크하게 되면 메모리를 조금 더 두어 check 연산을 O(1) 만큼의 복잡도로 처리할 수 있게 된다.

#define _CRT_SECURE_NO_WARNINGS

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


using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
int doqu[10][10];
int row[10][10];
int col[10][10];
int box[3][3][10];
vector<pii> zero;
bool dfs_check = false;

void do_memo(int tx, int ty, int x, int y, int i) {
	row[x][i] = 1;
	col[i][y] = 1;
	box[tx][ty][i] = 1;
	return;
}
void un_memo(int tx, int ty, int x, int y, int i) {
	row[x][i] = 0;
	col[i][y] = 0;
	box[tx][ty][i] = 0;
	return;
}
void print_doqu() {
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			printf("%d", doqu[i][j]);
		}
		printf("\n");
	}
	return;
}
void dfs(int n) {
	if (dfs_check) return;
	if (n == zero.size()) {
		dfs_check = true;
		print_doqu();
		return;
	}
	int cx = zero[n].first;
	int cy = zero[n].second;
	int tp = 0, tx, ty;
	for (int i = 1; i <= 9; i++) {
		if (row[cx][i] == 1) continue;
		if (col[i][cy] == 1) continue;
		tx = (cx - 1) / 3;
		ty = (cy - 1) / 3;
		if (box[tx][ty][i] == 1) continue;

		tp = doqu[cx][cy];
		doqu[cx][cy] = i;
		do_memo(tx, ty, cx, cy, i);
		dfs(n + 1);
		un_memo(tx, ty, cx, cy, i);
		doqu[cx][cy] = tp;
		
	}
	
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tx, ty;
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			scanf(" %1d", &doqu[i][j]);
			if (doqu[i][j] == 0)
				zero.push_back({ i,j });
			else {
				row[i][doqu[i][j]] = 1;
				col[doqu[i][j]][j] = 1;
				tx = (i - 1) / 3;
				ty = (j - 1) / 3;
				box[tx][ty][doqu[i][j]] = 1;
			}
		}
	}
	dfs(0);

	return 0;
}

전형적인 세그먼트 트리 문제이다. 일단 시간 제한이 2초이기 때문에 일일이 10만개의 정수 쌍 입력에 대해 10만개의 배열에서 최솟값과 최댓값을 뒤지게 되면 복잡도가 터지게 된다.

이를 위해 미리 답들을 트리 형태로 저장해놓는 세그먼트 트리를 사용하여 복잡도를 줄일 수 있다.

값을 저장할 때마다 최솟값과 최댓값을 log(n) 의 복잡도로 저장해놓는 식이다. 그 후 정수 쌍 입력을 받을 때마다 만들어 두었던 세그먼트 트리에 query를 날리는 식으로 문제를 풀게 되면 답이 금방 나오게 된다.

#define _CRT_SECURE_NO_WARNINGS

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


using namespace std;
typedef long long LL;
LL max_tree[1 << 20];
LL min_tree[1 << 20];
LL min_query_seg(int node, int s, int e, int l, int r) {
	if (r < s || e < l) return 1000000000;
	if (l <= s && e <= r) return min_tree[node];
	else
		return min(min_query_seg(node * 2, s, (s + e) / 2, l, r),
			min_query_seg(node * 2 + 1, (s + e) / 2 + 1, e, l, r));
	
}
LL max_query_seg(int node, int s, int e, int l, int r) {
	if (r < s || e < l) return 0;
	if (l <= s && e <= r) return max_tree[node];
	else 
		return max(max_query_seg(node * 2, s, (s + e) / 2, l, r),
			max_query_seg(node * 2 + 1, (s + e) / 2 + 1, e, l, r));
}
void update_seg(int node, int s, int e, int idx, int v) {
	if (idx < s || e < idx) return;
	if (s == e) {
		max_tree[node] = v;
		min_tree[node] = v;
	}
	else {
		update_seg(node * 2, s, (s + e) / 2, idx, v);
		update_seg(node * 2 + 1, (s + e) / 2 + 1, e, idx, v);
		max_tree[node] = max(max_tree[node * 2], max_tree[node * 2 + 1]);
		min_tree[node] = min(min_tree[node * 2], min_tree[node * 2 + 1]);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	LL n, m;
	LL a, b;
	scanf("%lld %lld", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a);
		update_seg(1, 1, n, i, a);
	}
	pair<LL, LL> ans;
	
	for (int i = 0; i < m; i++) {
		scanf("%lld %lld", &a, &b);
		printf("%lld ", min_query_seg(1, 1, n, a, b));
		printf("%lld\n", max_query_seg(1, 1, n, a, b));
	}
	
	return 0;
}

을 사용하는 문제였다.

일단 시간제한이 2초인데, 입력값이 (위치, 인구수) 쌍으로 10만개이다. 이를 일반적인 브루트포스로 풀게되면 전체 평균을 구하는 과정 중에 값의 범위 때문에 터질 수도 있다. 다만 시간으로는 안 터지지 않을까 싶다.

즉, 이 문제의 경우 그리디하게 위치를 정해주어야 하는데 그 로직은 다음과 같다.

1. 입력받은 쌍을 위치 순으로 정렬한다.
2. 해당 위치까지의 누적합을 배열에 저장해둔다.
3. 그 후 이분탐색으로 왼쪽 누적합, 오른쪽 누적합의 차이가 최소인 지점을 찾는다.

생각보다 간단한 로직이다. 허나 평균을 구하는게 아닌 누적합 자체로 이분탐색을 한다는 것 자체가 생각하기 어렵기 때문에 경험이 필요한 문제라 생각한다.

#define _CRT_SECURE_NO_WARNINGS

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


using namespace std;
typedef long long LL;

LL x[100001];
LL a[100001];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n;
	vector<pair<LL, LL>> v;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> a[i];
		v.push_back({ x[i], a[i] });
	}
	sort(v.begin(), v.end());

	vector<LL> sum;
	sum.push_back(v[0].second);
	for (int i = 1; i < n; i++) {
		sum.push_back(sum[i - 1] + v[i].second);
	}

	LL left = 0, right = n, mid;
	LL pos = 100000;
	while (left <= right) {
		mid = (left + right) / 2;
		if (sum[mid] < sum[n - 1] - sum[mid]) {
			left = mid + 1;
		}
		else if (sum[mid] > sum[n - 1] - sum[mid]) {
			right = mid - 1;
			pos = min(pos, v[mid].first);
		}
	}
	cout << pos;
	return 0;
}