https://www.acmicpc.net/problem/2661



1,2,3 세개의 숫자를 활용해서 길이 n의 수열을 만들면 된다.


기본적으로 여기까지는 백트래킹을 활용해서 진행해주면 된다.


이후에 나쁜 수열을 걸러내는 과정에서 substr을 적절히 활용해주면 되겠다.


주의할 점은, 검사를 재귀의 진입 부분에서 해야 한다는 것이다.



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
#include<iostream>
#include<set>
#include<string>
using namespace std;
int n, a[3] = { 1,2,3 }, arr[81];
string str = "";
set<string> ans;
bool ef = false;
void backTracking(int k) {
 
    str = "";
    for (int i = 0; i < k; i++)
        str += (arr[i] + '0');
    
    //부분 수열 존재 검사
    for (int i = 1; i <= k / 2; i++) { //수열 길이 절반까지만 확인하면 됨
        for (int j = 0; j <= k - 2 * i; j++) {
            if (str.substr(j, i) == str.substr(j + i, i)) {
                return;
            }
        }
    }
 
    //길이 n 완성
    if (k == n) {
        for (int i = 0; i < k; i++)
            cout << arr[i];
        exit(0); //가장 먼저 나오는 게 제일 작은 수열
        return;
    }
 
    for (int i = 0; i < 3; i++) {
        arr[k] = a[i];
        backTracking(k + 1);
        if (ef) return;
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    backTracking(0);
 
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1941 소문난 칠공주 C++  (0) 2019.08.10
백준 2023 신기한 소수 C++  (0) 2019.08.10
백준 2210번: 숫자판 점프 (C++)  (0) 2019.08.09
백준 2589번: 보물섬 (C++)  (0) 2019.08.09
백준 17069번: 파이프 옮기기 2 (C++)  (0) 2019.08.09

https://www.acmicpc.net/problem/2210


5 * 5의 격자판이 주어진다.


그 격자판에 있는 정수들을 활용해서 길이 6의 수열을 만들어야 한다.


이 때 사용했던 숫자라도 중복해서 사용할 수 있다.


또한, 숫자는 직전에 선택했던 숫자의 동서남북 방향에 위치한 숫자중에 하나로 선택해야 한다.



중복 제거를 간편하게 하기 위해서 set을 사용했다.



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
#include<iostream>
#include<set>
#include<string>
using namespace std;
int m[6][6];
string str = "";
set<int> res;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
void dfs(int depth, int row, int col, int cur) {
    if (depth == 5) { //depth가 0일때 이미 처음게 골라져있는 상태임
        res.insert(cur);
        
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        int nr = row + dr[i];
        int nc = col + dc[i];
        if (nr < 0 || nc < 0 || nr >= 5 || nc >= 5) continue;
        dfs(depth + 1, nr, nc, cur * 10 + m[nr][nc]);
    }
}
 
int main(void) {
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            cin >> m[i][j];
 
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            dfs(0, i, j, m[i][j]);
        }
    }
 
    cout << res.size();
 
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2023 신기한 소수 C++  (0) 2019.08.10
백준 2661 좋은수열 C++  (0) 2019.08.09
백준 2589번: 보물섬 (C++)  (0) 2019.08.09
백준 17069번: 파이프 옮기기 2 (C++)  (0) 2019.08.09
백준 17070번: 파이프 옮기기 1 (C++)  (0) 2019.08.09

https://www.acmicpc.net/problem/2589

 

2589번: 보물섬

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지

www.acmicpc.net

육지가 될 수 있는 땅 한 칸 한 칸에 대해 개별적으로 bfs를 수행해주면 된다.

 

방문처리를 거리 측정으로 하면서 최댓값을 구해주면 된다.

 

 

 

저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2661 좋은수열 C++  (0) 2019.08.09
백준 2210번: 숫자판 점프 (C++)  (0) 2019.08.09
백준 17069번: 파이프 옮기기 2 (C++)  (0) 2019.08.09
백준 17070번: 파이프 옮기기 1 (C++)  (0) 2019.08.09
백준 14890번: 경사로 (C++)  (0) 2019.08.09

https://www.acmicpc.net/problem/17069


간단한 DP 문제이다.


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
//1-indexed
#include<iostream>
 
using namespace std;
typedef long long ll;
ll m[33][33], d[33][33][3];
int main(void) {
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> m[i][j];
 
    d[1][2][0] = 1; //초기에는 1,2로 가로로 들어가는 방법 한가지
    d[1][2][1] = 0;
    d[1][2][2] = 0;
 
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == 1 && j <= 2) continue;
            if (m[i][j] == 1)  //현재 지점이 벽이면, 그 지점까지 오는 경로는 모두0 (그냥 스킵해도 초기화 0으로 되어있음)
                continue;
            
            if (m[i][j - 1] == 1) d[i][j][0] = 0; //가로로 들어오는 방법이 없는 경우 = 그 바로 왼쪽 벽인 경우
            else
                d[i][j][0] = d[i][j - 1][0] + d[i][j - 1][2];
 
            if (m[i - 1][j] == 1) d[i][j][1] = 0; //세로로 들어오는 방법이 없는 경우 = 그 바로 위쪽이 벽인 경우
            else
                d[i][j][1] = d[i - 1][j][1] + d[i - 1][j][2];
 
            if (m[i - 1][j] == 1 || m[i][j - 1] == 1) d[i][j][2] = 0; //대각으로 오는 방법이 없는 경우 = 날개 둘 중 하나라도 벽인 경우
            else
                d[i][j][2] = d[i - 1][j - 1][0] + d[i - 1][j - 1][1] + d[i - 1][j - 1][2];
        }
    }
 
    cout << d[n][n][0] + d[n][n][1] + d[n][n][2]; //모든 방향으로 들어오는 경우의 합
 
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2210번: 숫자판 점프 (C++)  (0) 2019.08.09
백준 2589번: 보물섬 (C++)  (0) 2019.08.09
백준 17070번: 파이프 옮기기 1 (C++)  (0) 2019.08.09
백준 14890번: 경사로 (C++)  (0) 2019.08.09
백준 14889번: 스타트와 링크 (C++)  (0) 2019.08.07

https://www.acmicpc.net/problem/17070


삼성 상시 검정 A형 기출 문제이다. 삼성의 문제이니만큼 완전탐색 혹은 시뮬레이션 문제일 것이다.


하지만 이를 생각하더라도, 동적계획법을 통해서 너무 쉬운 풀이가 가능하기 때문에 DP를 활용해서 간단하게 풀었다.


정점 i,j에 도착할 때, 어떤 방향 상태를 가지고 도착하는지 생각해보면, 세가지가 가능함을 알 수 있다.


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
//1-indexed
#include<iostream>
 
using namespace std;
int m[18][18], d[18][18][3];
int main(void) {
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> m[i][j];
 
    d[1][2][0] = 1; //초기에는 1,2로 가로로 들어가는 방법 한가지
    d[1][2][1] = 0;
    d[1][2][2] = 0;
 
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == 1 && j <= 2) continue;
            if (m[i][j] == 1)  //현재 지점이 벽이면, 그 지점까지 오는 경로는 모두0 (그냥 스킵해도 초기화 0으로 되어있음)
                continue;
            
            if (m[i][j - 1] == 1) d[i][j][0] = 0; //가로로 들어오는 방법이 없는 경우 = 그 바로 왼쪽 벽인 경우
            else
                d[i][j][0] = d[i][j - 1][0] + d[i][j - 1][2];
 
            if (m[i - 1][j] == 1) d[i][j][1] = 0; //세로로 들어오는 방법이 없는 경우 = 그 바로 위쪽이 벽인 경우
            else
                d[i][j][1] = d[i - 1][j][1] + d[i - 1][j][2];
 
            if (m[i - 1][j] == 1 || m[i][j - 1] == 1) d[i][j][2] = 0; //대각으로 오는 방법이 없는 경우 = 날개 둘 중 하나라도 벽인 경우
            else
                d[i][j][2] = d[i - 1][j - 1][0] + d[i - 1][j - 1][1] + d[i - 1][j - 1][2];
        }
    }
 
    cout << d[n][n][0] + d[n][n][1] + d[n][n][2]; //모든 방향으로 들어오는 경우의 합
 
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2589번: 보물섬 (C++)  (0) 2019.08.09
백준 17069번: 파이프 옮기기 2 (C++)  (0) 2019.08.09
백준 14890번: 경사로 (C++)  (0) 2019.08.09
백준 14889번: 스타트와 링크 (C++)  (0) 2019.08.07
백준 14891번: 톱니바퀴 (C++)  (0) 2019.08.07

+ Recent posts

티스토리툴바