고급반 7주차 풀이 - 으랏차차 (5 / 14)

1. [19321] Longest Increasing Subsequence (Gold IV)

예제가 너무 친절합니다.

\( f_{i} \)가 큰 값부터, 같다면 앞의 칸부터 시작해서 \( N \)부터 1까지 채워주면 됩니다.

이러면 동일한 레벨 or 낮은 레벨에서의 값은 무시하면서 진행되니 잘 되는 걸 볼 수 있습니다.

int arr[100020];
int ans[100020];

void Main(){
	int n; cin >> n;
	priority_queue<pi2> pq;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; pq.push({ arr[i], -i }); }
	for (int i = n; i >= 1; i--){
		int val = pq.top().fr, idx = -pq.top().sc; pq.pop();
		ans[idx] = i;
	}
	for (int i = 1; i <= n; i++){ cout << ans[i] << ' '; }
}

2. [13316] std::정렬부터 시작하는 디버깅 생활 (Gold II)

비교연산자를 생각해보면, 두 분수를 비교하는 Comparator임을 알 수 있습니다.

그런데 분모가 0이라면? 무슨 일이 일어날 지 모르게 됩니다. 아래 데이터처럼 잘 돌 수도 있어요.

4
0 0
0 1
1 1
1 0

3. [15640] Satan Game (Platinum IV)

칸은 크게 잡고, 주사위는 작게 잡으면 됩니다. 이제 그 주사위에 잘 맞게 뱀들을 놓으면 되는데...

아래처럼 그냥 딱 맞게 두면 WA를 받게 됩니다.

100 2 33
99 33
97 32
95 31
93 30
91 29
89 28
87 27
85 26
83 25
81 24
79 23
77 22
75 21
73 20
71 19
69 18
67 17
65 16
63 15
61 14
59 13
57 12
55 11
53 10
51 9
49 8
47 7
45 6
43 5
41 4
39 3
37 2
35 1

4. [25087] Halimtonian Tour (Platinum V)

그리드가 연결되어있다면, 항상 통행 가능합니다.

방법은 간단한데, DFS 돌리듯이 투어해주면 됩니다.

const int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, 1, 0, -1};
const string ds = "NESW";

int n, m; char mp[220][220];
int dir[420][420];

bool chk[220][220];
void dfs(int y, int x, int d){ d = d+3 & 3;
	chk[y][x] = 1;
	int c = 4; while (c--){
		int py = 2*y - (d==0 || d==1), px = 2*x - (d==0 || d==3);
		int yy = py+dy[d], xx = px+dx[d];
		bool flg = 1;
		if (1 > yy || yy > 2*n){ flg = 0; }
		else if (1 > xx || xx > 2*m){ flg = 0; }
		else if (mp[yy+1>>1][xx+1>>1] == '#'){ flg = 0; }
		else if (chk[yy+1>>1][xx+1>>1]){ flg = 0; }
		if (flg){ dir[py][px] = d; dfs(y+dy[d], x+dx[d], d); }
		else{
			if (c || y*x == 1){ dir[py][px] = d+1 & 3; }
			else{ dir[py][px] = d; }
		}
		d = d+1 & 3;
	}
}

void Main(){
	int t; cin >> t;
	for (int tt = 1; tt <= t; tt++){ cout << "Case #" << tt << ": ";
		memset(dir, -1, sizeof(dir)); memset(chk, 0, sizeof(chk));
		cin >> n >> m;
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= m; j++){ cin >> mp[i][j]; }
		}
		dfs(1, 1, 1);
		int py = 1, px = 1;
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= m; j++){
				if (mp[i][j] == '*' && !chk[i][j]){ cout << "IMPOSSIBLE"; goto done; }
			}
		}
		/*cout << endl;
		for (int i = 1; i <= 2*n; i++){
			for (int j = 1; j <= 2*m; j++){
				if (dir[i][j] >= 0){ cout << ds[ dir[i][j] ] << ' '; }
				else{ cout << ' ' << ' '; }
			}
			cout << endl;
		}*/
		while (1){
			int d = dir[py][px]; cout << ds[d];
			py += dy[d]; px += dx[d]; if (py==1 && px==1){ break; }
		}
		done: cout << endl;
	}
}

10. [21133] N-Queen 2 (Platinum III)

웰노운입니다 감사합니다

vector<int> f(int n){
	if (n&1){ vector<int> res = f(n-1); res.push_back(n); return res; }
	int m = n/2;
	vector<int> res;
	if (n%6 == 0){
		for (int i = 1; i <= m; i++){ res.push_back(2*i); }
		for (int i = 1; i <= m; i++){ res.push_back(2*i-1); }
		return res;
	}
	res.resize(n);
	for (int i = 1; i <= m; i++){ res[i-1] = 1 + (2*(i-1) + m-1) % n; }
	for (int i = m; i < n; i++){ res[i] = n+1 - res[m+m-i-1]; }
	return res;
}

void Main(){
	int n; cin >> n;
	for (int x : f(n)){ cout << x << endl; }
}

Not Solved

5. [19540] 인버스 ㄷㄷㄷㅈ (Diamond V)

6. [18913] Graph Coloring (Diamond IV)

7. [19552] 데이터 제작 (Diamond III)

8. [18762] Junk Problem (Ruby IV)

9. [2873] 롤러코스터 (Platinum III)

11. [2727] 2,3 거듭제곱의 합 (Platinum IV)

12. [20909] Impressive Integers (Platinum V)

13. [18929] Knights of Round Table (Diamond III)

14. [18759] Geometry PTSD (Diamond II)