BOJ : https://www.acmicpc.net/problem/14503

 

BOJ 14503번 로봇 청소기 문제입니다.

 

처음에는 이동가능한 곳 중에서 청소할 수 있는 모든 곳을 해야된다고 생각했습니다.

그래서 방문했던 곳(청소 한곳) 이여도 이 곳을 다시 방문하면 다른 방향에 청소를 할 수 있는 부분이 있을거라고

생각하고 문제를 풀었습니다.

 

문제를 잘못이해해서 예제출력부터 다르길래 다시 읽어봤습니다.

청소를 한 곳은 후진을 하지 않는 이상 이동을 하지 않는다는 조건이 있습니다...

 

딱히 어렵지 않으니 문제에서 요구하는대로 푸시면 될 것 같습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
using namespace std;
 
struct direct {
    int y, x;
}direct[4];
 
int N, M;
int r, c, d;
bool arr[52][52];
int visit[52][52];
 
void dfs(int y, int x, int dt, int cnt) {
    visit[y][x] = 1;
    int go;
    bool check = false;
    for (int i = 1; i <= 4; i++) {
        go = (dt+i)%4;
        int yy = y + direct[go].y;
        int xx = x + direct[go].x;
        if (yy>=0 && yy<N && xx>=0 && xx<M && !arr[yy][xx] && !visit[yy][xx]) {
            check = true;
            dfs(yy, xx, go, cnt + 1);
            return;
        }
    }
 
    if (!check) {
        int yy = y;
        int xx = x;
        if (dt == 0) xx -= 1;
        if (dt == 1) yy++;
        if (dt == 2) xx++;
        if (dt == 3) yy--;
 
        if (yy >= 0 && yy < N && xx >= 0 && xx < M && !arr[yy][xx])
            dfs(yy, xx, dt, cnt);
        else {
            cout << cnt;
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    direct[0] = { 0,1 };
    direct[1] = { -1,0 };
    direct[2] = { 0,-1 };
    direct[3] = { 1,0 };
 
    cin >> N >> M;
    cin >> r >> c >> d;
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> arr[i][j];
 
    int dt;
    if (d == 0) dt = 1;
    if (d == 1) dt = 0;
    if (d == 2) dt = 3;
    if (d == 3) dt = 2;
    dfs(r, c, dt, 1);
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

 

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1063번 킹  (0) 2020.04.07
BOJ 14499번 주사위 굴리기  (0) 2020.03.14
BOJ 3709번 레이저빔은 어디로  (0) 2020.03.13
BOJ 1043번 거짓말  (0) 2020.03.13
BOJ 1074번 Z  (0) 2020.03.05

BOJ : https://www.acmicpc.net/problem/3709

 

시뮬레이션 기본문제 입니다.

난이도는 높은편이 아니라서 문제에서 요구하는 대로 구현해주시면 됩니다.

설명이 필요할 것 같은 부분?은 주석처리했습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
using namespace std;
 
struct direct {
    int y, x;
}direct[4];
 
bool arr[52][52];
int n, r;
 
void dfs(int y, int x, int dt) {
    if (!y || !x || y == n + 1 || x == n + 1) {
        cout << y << " " << x << '\n';
        return;
    }
 
    // 꺽이면
    if (arr[y][x]) {
        int go = (dt + 1) % 4;
        dfs(y + direct[go].y, x + direct[go].x, go);
    }
    else {
        dfs(y + direct[dt].y, x + direct[dt].x, dt);
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    // 방향조절 (동->남->서->북)
    direct[0] = { 0,1 };
    direct[1] = { 1,0 };
    direct[2] = { 0,-1 };
    direct[3] = { -1,0 };
 
    int T; cin >> T;
    while (T--) {
        memset(arr, 0, sizeof(arr));
        cin >> n >> r;
        for (int i = 0; i < r; i++) {
            int x, y;
            cin >> y >> x;
            arr[y][x] = true;
        }
 
        int sy, sx;
        cin >> sy >> sx;
        // 위 -> 아래
        if (sy == 0) dfs(sy + 1, sx, 1);
        // 아래 -> 위
        if (sy == n + 1) dfs(sy - 1, sx, 3);
        // 왼쪽 -> 오른쪽
        if (sx == 0) dfs(sy, sx + 1, 0);
        // 오른쪽 -> 왼쪽
        if (sx == n + 1) dfs(sy, sx - 1, 2);
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
 

'algorithm > BOJ' 카테고리의 다른 글

BOJ 14499번 주사위 굴리기  (0) 2020.03.14
BOJ 14503번 로봇 청소기  (0) 2020.03.13
BOJ 1043번 거짓말  (0) 2020.03.13
BOJ 1074번 Z  (0) 2020.03.05
BOJ 1026번 보물  (0) 2020.02.28

BOJ : https://www.acmicpc.net/problem/1043

 

게시판을 보니 문제를 이해를 못하시는 분들이 꽤 되시는 것 같아서 문제 설명부터 하겠습니다.

 

간략하게 설명하자면,

진실을 아는 사람을 A, A가 속한 파티에 있는 사람을 B 라고 할 때

A,B 가 속한 모든 파티에서 거짓을 말하면 안됩니다.

 

결국 어떤 파티에서 A가 속하게 되면 => 이 파티 뿐만 아니라 다른 파티에서도 A, B 의 유무를 확인해야 됩니다.

 

예제를 보면

1 2

3

2 3 4

진실을 아는 사람이 만약 0이면 그냥 말그대로 파티 아무데서나 거짓말을 해도 된다가 되지만

만약 여기서 진실을 아는 사람이 2 이면?

파티1은 제외되고 일단 사람2가 파티2, 3에도 존재하는지 확인해봅니다.

파티2에는 사람3밖에 없으므로 거짓을 해도 됩니다. (아직까지는)

파티3에는 사람2가 존재하게 됩니다. => 나머지 사람 3, 4 가 참석할 다른 파티를 확인합니다.

사람3부터 확인하면 사람3은 파티2에 존재합니다. 결국 파티2는 거짓을 하면 안되게 됩니다.

 

이런방향으로 흘러가는 문제입니다.

처음에는 dfs를 통해서 짜보려고 했는데, 구현력이 떨어져서인지 구현이 잘 안되길래 bfs로 변경했습니다.

 

우선적으로 진실을 아는 사람을 모든 파티에 대해 확인할 때,

진실을 아는 사람이 파티에 참가하면 그 파티에 있는 사람까지 큐에 넣었습니다.

 

이 작업이 끝나면 큐에서 하나하나 꺼내면서 모든 파티를 확인해주시면 됩니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <string>
using namespace std;
 
int person, party, know;
vector<int> know_person;
bool party_person[52][52];
bool visit[52][52];
bool dont_party[52];
 
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    cin >> person >> party >> know;
    for (int i = 0; i < know; i++) {
        int n; cin >> n; know_person.push_back(n);
    }
    for (int i = 0; i < party; i++) {
        int n; cin >> n;
        for (int j = 0; j < n; j++) {
            int m; cin >> m; party_person[i][m] = true;
        }
    }
 
    queue<pair<int, int> > q;
    if (know == 0) cout << party;
    else {
        for (int i = 0; i < party; i++) {
            for (int j = 0; j < know; j++) {
                if (party_person[i][know_person[j]]) {
                    for (int k = 0; k < 52; k++) {
                        if (party_person[i][k])
                            q.push({ i,k });
                    }
                }
            }
        }
 
        while (!q.empty()) {
            int party_idx = q.front().first;
            int p = q.front().second;
            q.pop();
 
            if (visit[party_idx][p]) continue;
            visit[party_idx][p] = true;
            dont_party[party_idx] = true;
 
            for (int i = 0; i < party; i++) {
                if (party_person[i][p]) {
                    for (int j = 0; j < 52; j++) {
                        if (party_person[i][j]) q.push({ i,j });
                    }
                }
            }
        }
 
        int cnt = 0;
        for (int i = 0; i < party; i++) {
            if (dont_party[i] == false) cnt++;
        }
 
        cout << cnt;
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 14503번 로봇 청소기  (0) 2020.03.13
BOJ 3709번 레이저빔은 어디로  (0) 2020.03.13
BOJ 1074번 Z  (0) 2020.03.05
BOJ 1026번 보물  (0) 2020.02.28
BOJ 2240번 자두나무  (0) 2020.02.26

programmers : https://programmers.co.kr/learn/courses/30/parts/12263

 

programmers DP(동적계획법) level3 N으로 표현 문제입니다.

 

원래 dp 문제를 풀때 최적화되는 과정을 생각해보고

최적화를 위한 코드를 짜는게 맞긴한데

 

이 문제는 dp문제지만 어떤식으로 최적화를 해야되는건지 솔직히 모르겠다.

그래서 평소 dp문제를 풀 때 처럼 재귀로 문제를 풀었지만, 최적화..는 하지 못했다.

 

만약 dp를 제대로 풀기 위한 최적화방법을 고려해본다면..

N으로 만들 수 있는 모든 수 N,NN,NNN,NNNN,... 을 미리 8자리까지 만들어놓고

음.. dp[a][b] 의 2차원형태로 접근해본다면

a는 위에 미리 만들어놓은 값들, b는 만들어낼 수 있는 값들 (0~?????)

dp[a][b] 는 cnt 가 되겠다.

 

사실 문제풀때는 N을 8번 사용하라는 얘기 때문에 반복문을 8까지 돌렸는데

생각해보면 표현할 범위의 최대가 32000 이기 때문에

아무리 큰 숫자를 만든다고 해도 32000을 9로 곱한 수 인 288000 가 확인해볼 최댓값이 되겠다.

결국 8까지 돌려볼 필요도 없고, 최대 6자리까지만 만들어봐도 이 문제를 해결하는데 문제 없을 것 같았다.

 

 그래서 반복문을 6까지만 돌려 실행시켜봤는데 역시 AC를 받았다.

 

문제에 대한 설명은 코드에 있다

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int answer = 9;
int goal, N;
 
void dfs(long long total, int cnt){
    // total의 범위는 cnt에 의해 알아서 고려되므로 신경쓰지 않아도 된다
    if(cnt >= answer) return;
    if(total == goal){
        answer = min(answer, cnt);
        return;
    }
    
    // N 이라는 수를 갯수에 맞게 처리해야된다
    // N 이 5일때 555의 경우 N을 3번 사용한게 된다
    // 결국 재귀를 돌릴 때 N을 몆번사용했는지와 그 값을 함께 넘겨야한다
    // N은 최대 8번까지 사용하라고 했으니
    // 만약 N이 9이고 8번이면 99999999 이 되고, 곱하기연산을 수행하게 되면
    // int의 범위를 벗어날 수 있으니 total는 long long을 사용한다
    int num = 0;
    for(int i = 1; i<9; i++){
        num *= 10, num += N;
        
        dfs(total + num, cnt + i);
        dfs(total - num, cnt + i);
        
        // N을 최소로 사용해야 하는데 만약 total이 0일 경우 곱하기나 나눗셈을 하면
        // 최소횟수를 만들 수 없다
        if(total != 0){
            dfs(total * num, cnt+i);
            dfs(total / num, cnt+i);
        }
    }
}
 
int solution(int n, int number) {
    // 재귀를 통해서 접근해보자
    N = n, goal = number;
    
    dfs(0, 0);
    answer = answer >= 9 ? -1 : answer;
    return answer;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > programmers' 카테고리의 다른 글

Programmers 소수 찾기 C++  (0) 2020.07.03
Programmers 라면공장(C++)  (0) 2020.07.02
programmers 전화번호 목록  (0) 2020.03.10
programmers H-Index C++  (0) 2020.03.10
programmers 가장 큰 수  (0) 2020.03.10

+ Recent posts

티스토리툴바