오늘의 문제
14890 경사로
15684 사다리 조작
15684 드래곤 커브
14890 경사로
코드
#include <bits/stdc++.h>
using namespace std;
int n, l;
int board[101][101];
int street(vector<int> line) {
int idx = 0, cnt = 1;
while (idx < n - 1) {
if (abs(line[idx] - line[idx + 1]) > 1) return 0;
if (line[idx] == line[idx + 1]) {
idx++; cnt++;
}
else if (line[idx] < line[idx + 1]) {
if (cnt < l) return 0;
idx++; cnt = 1;
}
else {
if (idx + l >= n) return 0;
for (int i = idx + 1; i < idx + l; i++) {
if (line[i] != line[i + 1]) return 0;
}
idx = idx + l; cnt = 0;
}
}
return 1;
}
int main() {
cin >> n >> l;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> board[i][j];
}
}
int cnt = 0;
for (int i = 0; i < n; i++) {
vector<int> line;
for (int j = 0; j < n; j++) {
line.emplace_back(board[i][j]);
}
cnt += street(line);
}
for (int i = 0; i < n; i++) {
vector<int> line;
for (int j = 0; j < n; j++) {
line.emplace_back(board[j][i]);
}
cnt += street(line);
}
cout << cnt;
}15684 사다리 조작
코드
#include <bits/stdc++.h>
using namespace std;
int n, m, h; // n : 세로, m : 가로, h : 가로 점선
vector<vector<int>> ladder;
int dx[3] = { 1, 1, 1 };
int dy[3] = { 0, 1, -1 };
bool down() {
for (int i = 0; i < n; i++) { // 각 열 별로 시행
int c = i, r = 0;
while (r < h) {
c += dy[ladder[r][c]];
r += dx[ladder[r][c]];
}
if (c != i) return false;
}
return true;
}
int dfs(int k, int st) {
if (k == 4) return -1;
for (int i = st; i < (n - 1) * h; i++) {
if (ladder[i / (n - 1)][i % (n - 1)] != 0 || ladder[i / (n - 1)][i % (n - 1) + 1] != 0) {
continue;
}
ladder[i / (n - 1)][i % (n - 1)] = 1;
ladder[i / (n - 1)][i % (n - 1) + 1] = 2;
if (down()) return k;
else {
dfs(k + 1, i + 1);
ladder[i / (n - 1)][i % (n - 1)] = 0;
ladder[i / (n - 1)][i % (n - 1) + 1] = 0;
}
}
}
int back_tracking() {
// 추가 X
if (down()) return 0;
int cnt = 5;
for (int i = 0; i < (n - 1) * h; i++) {
if (ladder[i / (n - 1)][i % (n - 1)] != 0 || ladder[i / (n - 1)][i % (n - 1) + 1] != 0) {
continue;
}
ladder[i / (n - 1)][i % (n - 1)] = 1;
ladder[i / (n - 1)][i % (n - 1) + 1] = 2;
if (down()) cnt = min(cnt, 1); // 1일 때는 바로 return해도 될 것 같다
for (int j = i + 1; j < (n - 1) * h; j++) {
if (ladder[j / (n - 1)][j % (n - 1)] != 0 || ladder[j / (n - 1)][j % (n - 1) + 1] != 0) {
continue;
}
ladder[j / (n - 1)][j % (n - 1)] = 1;
ladder[j / (n - 1)][j % (n - 1) + 1] = 2;
if (down()) cnt = min(cnt, 2);
for (int k = j + 1; k < (n - 1) * h; k++) {
if (ladder[k / (n - 1)][k % (n - 1)] != 0 || ladder[k / (n - 1)][k % (n - 1) + 1] != 0) {
continue;
}
ladder[k / (n - 1)][k % (n - 1)] = 1;
ladder[k / (n - 1)][k % (n - 1) + 1] = 2;
if (down()) cnt = min(cnt, 3);
ladder[k / (n - 1)][k % (n - 1)] = 0;
ladder[k / (n - 1)][k % (n - 1) + 1] = 0;
}
ladder[j / (n - 1)][j % (n - 1)] = 0;
ladder[j / (n - 1)][j % (n - 1) + 1] = 0;
}
ladder[i / (n - 1)][i % (n - 1)] = 0;
ladder[i / (n - 1)][i % (n - 1) + 1] = 0;
}
return cnt == 5 ? -1 : cnt;
}
int main() {
cin >> n >> m >> h;
ladder = vector<vector<int>>(h, vector<int>(n, 0));
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
ladder[a - 1][b - 1] = 1;
ladder[a - 1][b] = 2;
}
cout << back_tracking();
}백트래킹은 헷갈린다...ㅜㅜ 난 재귀로 푸는 것보다 for문을 돌리는 게 나은 것 같다.
처음에는 시간 초과가 났다. 원인은 자명하다.
사다리 2개 놓을 때와 3개 놓을 때를 각각 조합을 구해서 했기 때문.
그리고 이 문제에서는 사다리를 최소로 설치했을 때를 구해야하므로 문제가 해결되자마자 바로 재귀의 깊이를 return하면 안 되고, 이후에 더 작은 값이 나올 수 있으므로 min 함수를 이용해서 최솟값을 갱신해야 했다. 이걸 안 하면 12%에서 실패뜬다..
시간초과 코드
#include <bits/stdc++.h>
using namespace std;
int n, m, h; // n : 세로, m : 가로, h : 가로 점선
vector<vector<int>> ladder, tmp;
int dx[3] = { 1, 1, 1 };
int dy[3] = { 0, 1, -1 };
void copy() {
tmp = vector<vector<int>>(h, vector<int>(n, 0));
for (int i = 0; i < h; i++) {
for (int j = 0; j < n; j++) {
tmp[i][j] = ladder[i][j];
}
}
}
bool down() {
for (int i = 0; i < n; i++) { // 각 열 별로 시행
int c = i, r = 0;
while (r < h) {
c += dy[tmp[r][c]];
r += dx[tmp[r][c]];
}
if (c != i) return false;
}
return true;
}
int back_tracking() {
// 추가 X
copy();
if (down()) return 0;
// 1개 추가
for (int i = 0; i < h; i++) {
for (int j = 0; j < n - 1; j++) {
if (ladder[i][j] == 0) {
copy();
tmp[i][j] = 1;
tmp[i][j + 1] = 2;
if (down()) return 1;
}
}
}
// 2개 추가
vector<int> arr((n - 1) * h, 1);
arr[0] = 0, arr[1] = 0;
do {
bool able = true;
copy();
for (int i = 0; i < (n - 1) * h; i++) {
if (!arr[i]) {
if (tmp[i / (n - 1)][i % (n - 1)] != 0 || tmp[i / (n - 1)][i % (n - 1) + 1] != 0) {
able = false;
break;
}
tmp[i / (n - 1)][i % (n - 1)] = 1;
tmp[i / (n - 1)][i % (n - 1) + 1] = 2;
}
}
if (able) {
if (down()) return 2;
}
} while (next_permutation(arr.begin(), arr.end()));
// 3개 추가
arr = vector<int>((n - 1) * h, 1);
arr[0] = 0; arr[1] = 0; arr[2] = 0;
do {
bool able = true;
copy();
for (int i = 0; i < (n - 1) * h; i++) {
if (!arr[i]) {
if (tmp[i / (n - 1)][i % (n - 1)] != 0 || tmp[i / (n - 1)][i % (n - 1) + 1] != 0) {
able = false;
break;
}
tmp[i / (n - 1)][i % (n - 1)] = 1;
tmp[i / (n - 1)][i % (n - 1) + 1] = 2;
}
}
if (able) {
if (down()) return 3;
}
} while (next_permutation(arr.begin(), arr.end()));
return -1;
}
int main() {
cin >> n >> m >> h;
ladder = vector<vector<int>>(h, vector<int>(n, 0));
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
ladder[a - 1][b - 1] = 1;
ladder[a - 1][b] = 2;
}
cout << back_tracking();
}15685 드래곤 커브
코드
#include <bits/stdc++.h>
using namespace std;
int n, x, y, d, g;
int board[101][101];
void dragon() {
vector<int> dir;
dir.emplace_back(d);
while (g--) {
int vs = dir.size();
for (int i = vs - 1; i >= 0; i--) {
dir.emplace_back((dir[i] + 1) % 4);
}
}
board[y][x] = 1;
for (int i : dir) {
if (i == 0) ++x;
else if (i == 1) --y;
else if (i == 2) --x;
else ++y;
board[y][x] = 1;
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x >> y >> d >> g;
dragon();
}
int cnt = 0;
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
if (!board[i][j]) continue;
if (!board[i + 1][j]) continue;
if (!board[i][j + 1]) continue;
if (!board[i + 1][j + 1]) continue;
++cnt;
}
}
cout << cnt;
}어려웠다.. 방향을 먼저 구하고 좌표를 계산하는 방식을 떠올리지 못했다.
HICE 19