반응형

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

 

9663번: N-Queen

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

퀸의 특성을 이해하면 쉽게 풀 수 있는 문제입니다.

 

 

퀸은 가로 세로 대각선 방향의 모든 기물을 잡을 수 있습니다. 따라서 한 줄에는 하나의 퀸만 있을 수 있다는 점을 활용하여서 퀸을 놓을 때마다 좌표를 배열에 저장해줍니다.

 

재귀 호출을 할 때 퀸을 놓을 때마다 y값을 1씩 증가시킬 예정이므로 y값은 따로 저장하지 않습니다.

 

qx [15], up [30], down [30] 배열을 만들어 qx 배열에는 퀸의 x좌표를 up 배열에는 오른쪽 위 대각선 방향의 좌표, down 배열에는 오른쪽 아래 대각선 방향의 좌표를 각각 저장해줍니다.

 

또한 대각선 방향의 좌표들의 특성은 아래와 같기 때문에 up [y+x], down [y-x+N-1]을 각각 저장해 주어 퀸의 대각선 방향에 다른 퀸이 있는지 체크할 수 있습니다.

 

 

[ 소스 코드 ]

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
#include <iostream>
 
using namespace std;
 
int N;
int qx[15];        //퀸의 x좌표 저장
int up[30];        //퀸의 오른쪽 위 대각선 방향 체크
int down[30];    //퀸의 오른쪽 아래 대각선 방향 체크
int cnt;
int ans;
 
int check(int y, int x)    //y,x 좌표에 퀸을 놓을 수 있는지 체크하는 함수
{
    if (qx[x] || up[y + x] || down[y - x + N - 1]) {
        return 0;        //놓을 수 없다면 0 return
    }
 
    return 1;            //놓을 수 있다면 1 return
}
 
void dfs(int y)            //한 줄에 하나의 퀸만 들어갈 수 있으므로 
{                        //퀸을 놓으면 바로 y+1값으로 dfs 진행
    if (cnt == N) {
        ans++;
        return;
    }
    if (y >= N) {
        return;
    }
 
    for (int x = 0; x < N; x++) {
        if (check(y, x))
        {
            qx[x]++;        //x좌표 저장
            up[y + x]++;    //대각선 방향 저장
            down[y - x + N - 1]++;
            cnt++;
            dfs(y + 1);
            cnt--;
            qx[x]--;
            up[y + x]--;
            down[y - x + N - 1]--;
        }
    }
}
 
int main()
{
    cin >> N;
 
    dfs(0);
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1238번 - 파티 (C++)  (0) 2022.06.09
[ 백준 ] 12865번 - 평범한 배낭 (C++)  (0) 2022.06.08
[ 백준 ] 1504번 - 특정한 최단 경로 (C++)  (0) 2022.06.06
[ 백준 ] 11054번 - 가장 긴 바이토닉 부분 수열 (C++)  (0) 2022.06.05
[ 백준 ] 11779번 - 최소비용 구하기 2 (C++)  (0) 2022.06.04
반응형

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

 

1504번: 특정한 최단 경로

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존

www.acmicpc.net

 

 

[ 문제풀이 ]

 

쉬운 다익스트라 문제였습니다.

 

다만 경로를 쪼개서 구해야 했고, 경우의 수가 두 가지가 있기 때문에 두 번의 계산 중 더 작은 값이 답이 되었습니다.

 

1 -> v1 -> v2 -> N

1 -> v2 -> v1 -> N

 

이 두가지 경우 중 더 거리가 짧은 경우가 답이 됩니다.

 

[ 소스 코드 ]

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
struct Node {
    int to;
    int cost;
};
 
struct cmp {
    bool operator()(Node right, Node left)
    {
        return left.cost < right.cost;
    }
};
 
int N, E;
vector<Node> list[801];
int v[2];
 
int dijkstra(int start, int end)        //시작점과 도착점의 최단거리를 return하는 dijkstra함수
{
    priority_queue<Node, vector<Node>, cmp> pq;
    pq.push({ start, 0 });
    int visited[801] = { 0 };
 
    while (!pq.empty())
    {
        int to = pq.top().to;
        int cost = pq.top().cost;
        pq.pop();
 
        if (visited[to] == 1) continue;
        visited[to] = 1;
 
        if (to == end)
        {
            return cost;
        }
 
        for (int i = 0; i < list[to].size(); i++) {
            int next = list[to][i].to;
            int nextCost = list[to][i].cost;
            if (visited[next] != 1) {
                pq.push({ next, cost + nextCost });
            }
        }
    }
 
    return -1;
}
 
int main()
{
    cin >> N >> E;
 
    for (int i = 0; i < E; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        list[a].push_back({ b,c });
        list[b].push_back({ a,c });
    }
 
    for (int i = 0; i < 2; i++) {
        cin >> v[i];
    }
 
    int a1 = dijkstra(1, v[0]);
    int b1 = dijkstra(1, v[1]);
    int mid = dijkstra(v[0], v[1]);
    int a2 = dijkstra(v[1], N);
    int b2 = dijkstra(v[0], N);
 
    int min = a1 + mid + a2;        //1 -> v[0] -> v[1] -> N
 
    if (a1 != -1 && a2 != -1 && mid != -1) {
        if (min > b1 + mid + b2) {    //1 -> v[1] -> v[0] -> N
            min = b1 + mid + b2;
        }
    }
    else {        //경로가 없다면
        cout << -1;
        return 0;
    }
 
    cout << min;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 12865번 - 평범한 배낭 (C++)  (0) 2022.06.08
[ 백준 ] 9663번 - N-Queen (C++)  (0) 2022.06.07
[ 백준 ] 11054번 - 가장 긴 바이토닉 부분 수열 (C++)  (0) 2022.06.05
[ 백준 ] 11779번 - 최소비용 구하기 2 (C++)  (0) 2022.06.04
[ 백준 ] 17070번 - 파이프 옮기기 1 (C++)  (0) 2022.06.03
반응형

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

 

11054번: 가장 긴 바이토닉 부분 수열

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

가장 긴 증가하는 부분 수열을 구하는 문제를 풀어보고 풀어보시기를 추천드립니다!

 

먼저 각 idx의 증가하는 부분 수열 길이의 최댓값을 increase 배열에 lower_bound를 활용하여 저장해줍니다. 마찬가지로 감소하는 부분 수열은 배열의 끝부분에서부터 시작하여 부분 수열 길이의 최댓값을 decrease 배열에 lower_bound를 활용하여 저장해줍니다.

 

다음으로 0번째 idx부터 N-1번째 idx까지 increase 배열과 decrease 배열을 더한 값에 -1을 해준 후 최댓값을 max에 저장해준 뒤 출력하면 답을 쉽게 구할 수 있습니다.

 

-1을 해주는 이유는 특정 idx에서 increase 배열과 decrease 배열이 한번 겹치기 때문입니다.

 

 

[ 소스 코드 ]

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
#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int arr[1000];
int increase[1000];
int decrease[1000];
vector<int> mem;
 
int N;
 
int main()
{
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
 
    int max = 1;
 
    for (int i = 0; i < N; i++) {        //증가하는 부분 수열의 최대 길이 increase에 저장
        if (i == 0) {
            mem.push_back(arr[i]);
        }
        else {
            if (mem[mem.size() - 1] < arr[i]) {
                max++;
                mem.push_back(arr[i]);
            }
            else {
                int idx = lower_bound(mem.begin(), mem.end(), arr[i]) - mem.begin();
                mem[idx] = arr[i];
            }
        }
        increase[i] = max;
    }
 
    max = 1;
    mem.clear();
 
    for (int i = N-1; i >= 0; i--) {    //감소하는 부분 수열의 최대 길이 decrease에 저장
        if (i == N-1) {
            mem.push_back(arr[i]);
        }
        else {
            if (mem[mem.size() - 1] < arr[i]) {
                max++;
                mem.push_back(arr[i]);
            }
            else {
                int idx = lower_bound(mem.begin(), mem.end(), arr[i]) - mem.begin();
                mem[idx] = arr[i];
            }
        }
        decrease[i] = max;
    }
 
    max = 0;
 
    for (int i = 0; i < N; i++) {        //한 점에서 증가 수열과 감소 수열의 수가 하나 겹치므로 -1을 해줌
        if (max < increase[i] + decrease[i] - 1) {
            max = increase[i] + decrease[i] - 1;    //최댓값 저장
        }
    }
 
    cout << max;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 9663번 - N-Queen (C++)  (0) 2022.06.07
[ 백준 ] 1504번 - 특정한 최단 경로 (C++)  (0) 2022.06.06
[ 백준 ] 11779번 - 최소비용 구하기 2 (C++)  (0) 2022.06.04
[ 백준 ] 17070번 - 파이프 옮기기 1 (C++)  (0) 2022.06.03
[ 백준 ] 9251번 - LCS (C++)  (0) 2022.06.02
반응형

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

 

11779번: 최소비용 구하기 2

첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스

www.acmicpc.net

 

 

 

[ 문제풀이 ]

 

일반적인 최소 거리를 구하는 다익스트라 문제였습니다. 하지만 거기에 경로를 출력하라는 요구사항이 있었기 때문에 조금 더 복잡했지만 몇 줄 추가만 해주면 쉽게 풀리는 문제였습니다.

 

Bus struct 안에 경로를 저장할 vector를 추가해 주었고, 이를 pq에 넣어주면 각 인자별로 경유지를 따로 저장할 수 있기 때문에 목적지에 도착했을 때 이 경유지를 따로 저장만 해주면 됩니다.

 

[ 소스 코드 ]

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
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
struct Bus {                    //노선의 정보를 저장할 struct
    int to;
    int cost;
    vector<int> via;
};
 
int n, m;
int visited[1001];            //방문 여부 체크
vector<Bus> list[1001];        //버스 도착지와 cost를 저장할 vector list
 
bool cmp(Bus left, Bus right)    //가격이 낮은 순으로 list를 정렬
{
    return left.cost < right.cost;
}
 
struct comp {                    //가격이 낮은 순으로 priority_queue에서 빠져나옴
    bool operator()(Bus right, Bus left)
    {
        return left.cost < right.cost;
    }
};
 
int main()
{
    int start, end;
    int ans;                //총 가격 저장할 변수
    vector<int> ansVia;        //경로를 저장할 vector
    cin >> n >> m;
 
    for (int i = 0; i < m; i++) {    //노선 정보를 list에 입력
        int start, end, cost;
        scanf("%d %d %d", &start, &end, &cost);
        list[start].push_back({ end,cost });
    }
 
    cin >> start >> end;
 
    for (int i = 1; i <= n; i++) {    //가격이 낮은 순으로 정렬
        sort(list[i].begin(), list[i].end(), cmp);
    }
 
    priority_queue<Bus, vector<Bus>, comp> pq;
    vector<int> via;
    pq.push({ start,0, via});        //시작점을 pq에 넣기
    
 
    while (!pq.empty())
    {
        int to = pq.top().to;
        int cost = pq.top().cost;
        vector<int> via = pq.top().via;
 
        pq.pop();
 
        if (visited[to] == 1) continue;    //방문했다면 continue
        visited[to]++;
        via.push_back(to);
 
        if (to == end) {        //목적지에 도착하면 비용과 경로를 저장
            ans = cost;
            ansVia = via;
            break;
        }
 
        for (int i = 0; i < list[to].size(); i++) {
            int next = list[to][i].to;
            int nextCost = list[to][i].cost;
            if (visited[next] != 1) {        //방문하지 않았다면
                pq.push({ next, cost + nextCost, via});    //다음 노드와 여기까지 오는데 드는 비용, 경로를 pq에 넣기
            }
        }
    }
 
    printf("%d\n%d\n", ans, ansVia.size());        //출력
    for (int i = 0; i < ansVia.size(); i++) {
        printf("%d ", ansVia[i]);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1504번 - 특정한 최단 경로 (C++)  (0) 2022.06.06
[ 백준 ] 11054번 - 가장 긴 바이토닉 부분 수열 (C++)  (0) 2022.06.05
[ 백준 ] 17070번 - 파이프 옮기기 1 (C++)  (0) 2022.06.03
[ 백준 ] 9251번 - LCS (C++)  (0) 2022.06.02
[ 백준 ] 15686번 - 치킨 배달 (C++)  (0) 2022.06.01
반응형

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

 

17070번: 파이프 옮기기 1

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제는 여러 가지 방법으로 풀 수 있습니다. dfs를 이용하여 모든 경우의 수를 다 구할 수도 있고, dp를 이용해서 더 빠르게 풀 수도 있습니다.

 

그중 dp를 이용한 방법에 대해서 설명드리겠습니다. 어떤 한 좌표에 파이프가 올 수 있는 경우의 수를 dp [ state ][ y ][ x ] 배열에 각각 저장하면서 마지막에 dp [ 0 ][ N ][ N ] + dp [ 1 ][ N ][ N ] + dp [ 2 ][ N ][ N ]을 출력하면 됩니다. 

 

먼저 한 점 y, x에 올 수 있는 파이프의 개수를 저장하기 위해서는 각각의 상황에 따라 다르게 구해주어야합니다.

 

예를 들어 0번 상태(가로) 일 때는 1번 상태(세로)의 파이프는 올 수 없습니다. 따라서, dp [ 0 ][ y ][ x ] = dp[ 0 ][ y ][ x - 1 ] + dp[ 2 ][ y ][ x - 1 ]이 됩니다. 마찬가지로 나머지 상태에서도 값을 구해주면 답을 얻을 수 있습니다.

 

다음 소스 코드에는 두 가지 방법을 모두 나타내었습니다. 

[ 소스 코드 ]

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
 
using namespace std;
 
int N;
int arr[17][17];
int dp[3][17][17];            //각 상태를 저장할 dp배열 [state][y][x] state 0:가로 1:세로 2:대각
 
int main()
{
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> arr[i][j];
        }
    }
 
    dp[0][1][2] = 1;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (arr[i][j] != 1) {        //파이프가 움직일 수 있을 때만
                dp[0][i][j] += dp[0][i][j - 1] + dp[2][i][j - 1];    //가로, 대각
                dp[1][i][j] += dp[1][i - 1][j] + dp[2][i - 1][j];    //세로, 대각
                if (arr[i - 1][j] != 1 && arr[i][j - 1] != 1) {
                    for (int k = 0; k < 3; k++) {
                        dp[2][i][j] += dp[k][i - 1][j - 1];        //가로, 세로, 대각
                    }
                }
            }
        }
    }
 
    int ans = 0;
    for (int i = 0; i < 3; i++) {
        ans += dp[i][N][N];
    }
 
    cout << ans;
}
 
//#include <iostream>
//
//using namespace std;
//
//int N;
//int arr[16][16];
//int dp[3][16][16];
//int dx[3] = { 1,0,1 };
//int dy[3] = { 0,1,1 };
//
//void dfs(int state, int y, int x)
//{
//    if (dp[state][y][x] != -1) return;
//
//    int cur = 0;
//
//    if (state != 1 && arr[y][x + 1] == 0 && x + 1 < N) {
//        dfs(0, y, x + 1);
//        cur += dp[0][y][x + 1];
//    }
//
//    if (state != 0 && arr[y + 1][x] == 0 && y + 1 < N) {
//        dfs(1, y + 1, x);
//        cur += dp[1][y + 1][x];
//    }
//
//    bool flag = true;
//
//    for (int i = 0; i < 3; i++) {
//        int yy = y + dy[i];
//        int xx = x + dx[i];
//        if (arr[yy][xx] != 0) {
//            flag = false;
//            break;
//        }
//    }
//
//    if (flag && x + 1 < N && y + 1 < N) {
//        dfs(2, y + 1, x + 1);
//        cur += dp[2][y + 1][x + 1];
//    }
//
//    dp[state][y][x] = cur;
//}
//
//int main()
//{
//    cin >> N;
//    for (int i = 0; i < N; i++) {
//        for (int j = 0; j < N; j++) {
//            cin >> arr[i][j];
//            for (int k = 0; k < 3; k++) {
//                if (i == N - 1 && j == N - 1) {
//                    dp[k][i][j] = 1;
//                }
//                else {
//                    dp[k][i][j] = -1;
//                }
//            }
//        }
//    }
//
//    dfs(0, 0, 1);
//
//    cout << dp[0][0][1];
//}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 11054번 - 가장 긴 바이토닉 부분 수열 (C++)  (0) 2022.06.05
[ 백준 ] 11779번 - 최소비용 구하기 2 (C++)  (0) 2022.06.04
[ 백준 ] 9251번 - LCS (C++)  (0) 2022.06.02
[ 백준 ] 15686번 - 치킨 배달 (C++)  (0) 2022.06.01
[ 백준 ] 1149번 - RGB거리 (C++)  (0) 2022.05.31
반응형

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

 

9251번: LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

LCS란 Longest Common Subsequence 즉, 최장 공통부분 수열을 찾는 것입니다. 이 문제는 모든 수열의 부분수열 중에서 공통이 되는 가장 긴 수열의 길이를 구하는 문제입니다.

 

가장 긴 수열을 찾기 위해서는 각 수열의 요소들을 하나씩 비교해서 만약 같다면 바로 전의 최장 수열 길이의 최댓값에 +1을 해주고 같지 않다면 이전의 최장 수열 길이 중 최댓값을 대입해주면 됩니다.

 

이해하기 쉽게 다음 두 수열을 예로 들어서 설명하겠습니다.

ACAYKP
CAPCAK

먼저 문자열의 최대 길이는 1000이므로 dp[ 1001 ][ 1001 ]의 배열을 만들어줍니다. 그리고 각각의 값들을 비교하면서 위에서 설명한 대로 값들을 대입합니다. 쉬운 비교를 위해서 모든 수열의 0번째 요소를 1번으로 설정합니다.

 

 

다음으로 각 요소들을 비교해가면서 서로 같은 문자라면 dp [ i - 1 ][ j - 1 ] + 1의 값을 대입해줍니다.

 

그렇지 않다면 바로 직전까지의 수열의 최댓값 즉, dp[dp [ i - 1 ][ j ]와 dp [ i ][ j - 1 ] 중 더 큰 값을 대입해줍니다.

 

먼저 str[ 0 ][ 1 ]인 'A'와 str [ 1 ][ 1 ]인 'C'는 서로 다르기 때문에 dp [ 0 ][ 1 ]과 dp [ 1 ][ 0 ]중 더 큰 값을 dp [ 1 ][ 1 ]에 대입해줍니다.

 

다음으로 str[ 0 ][ 1 ]인 'A'와 str [ 1 ][ 2 ]인 'A'는 서로 같으므로 dp [ 0 ][ 1 ] + 1을 dp [ 1 ][ 2 ]에 대입해줍니다. 이런 식으로 쭉 대입을 해주다 보면 다음과 같은 표가 완성됩니다.

 

 

그리고 마지막에 dp[ 6 ][ 6 ]을 출력해주면 가장 긴 부분 수열의 길이를 구할 수 있습니다.

 

[ 소스 코드 ]

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
#include <iostream>
#include <string>
 
using namespace std;
 
int dp[1001][1001];
 
int main()
{
    string str[2];
 
    for (int i = 0; i < 2; i++) {
        cin >> str[i];
        str[i] = '0' + str[i];        //수열을 1부터 시작하기 위해서 맨 앞에 더미 문자를 넣음
    }
 
    for (int i = 1; i < str[0].size(); i++) {
        for (int j = 1; j < str[1].size(); j++) {    //각 문자들을 비교하며 최장 부분수열의 길이를 경신
            if (str[0][i] == str[1][j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
 
    cout << dp[str[0].size() - 1][str[1].size()-1];
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 11779번 - 최소비용 구하기 2 (C++)  (0) 2022.06.04
[ 백준 ] 17070번 - 파이프 옮기기 1 (C++)  (0) 2022.06.03
[ 백준 ] 15686번 - 치킨 배달 (C++)  (0) 2022.06.01
[ 백준 ] 1149번 - RGB거리 (C++)  (0) 2022.05.31
[ 백준 ] 1799번 - 비숍 (C++)  (0) 2022.05.30
반응형

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

 

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제의 핵심은 조합을 뽑을 수 있는가 없는가입니다.

 

주어지는 치킨집들 중에서 맥시멈의 치킨집들을 조합으로 모두 뽑아내서 각 치킨집 중 가장 가까운 치킨집들의 거리를 각각 sum에 더해주고 그중 가장 작은 값을 ans에 경신시켜주어서 답을 내면 되는 아주 간단한 방식입니다.

 

처음에는 bfs를 통해서 가장 가까운 치킨집을 구하려고 했었지만 문제에도 나와있듯이 치킨집까지의 거리는 |r1-r2| + |c1-c2|이므로 조합으로 뽑은 모든 치킨집에 대입시켜 가장 가까운 치킨집을 선택하면 됩니다.

 

[ 소스 코드 ]

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
#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
struct pos {            //각 좌표를 저장하기 위한 pos struct
    int y;
    int x;
};
 
int N, M;    
int arr[50][50];        //맵
vector<pos> chicken;    //치킨집의 좌표를 저장할 vector
pos box[13];            //조합을 저장할 배역
int sum;
int ans = 987654321;
 
void dfs(int level, int num)
{
    if (level == M)
    {
        sum = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == 1) {
                    int min = 987654321;
                    for (int k = 0; k < M; k++) {
                        int y = box[k].y;        //조합으로 뽑은 치킨집의 좌표를 추출
                        int x = box[k].x;        //거리를 계산 후 dist에 저장
                        int dist = abs(y - i) + abs(x - j);
                        if (min > dist) {        //가장 작은 dist를 min에 저장
                            min = dist;
                        }
                    }
                    sum += min;            //sum에 min을 더함
                }
            }
        }
        if (ans > sum) {            //가장 작은 sum을 ans에 경신
            ans = sum;
        }
        return;
    }
 
    for (int i = num; i < chicken.size()-M+1+level; i++) {
        box[level] = chicken[i];
        dfs(level + 1, i + 1);
        box[level] = { 0,0 };
    }
}
 
int main()
{
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];        
            if (arr[i][j] == 2) {    //치킨집들을 chicken vector에 push
                chicken.push_back({ i,j });
            }
        }
    }
 
    dfs(0, 0);
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 17070번 - 파이프 옮기기 1 (C++)  (0) 2022.06.03
[ 백준 ] 9251번 - LCS (C++)  (0) 2022.06.02
[ 백준 ] 1149번 - RGB거리 (C++)  (0) 2022.05.31
[ 백준 ] 1799번 - 비숍 (C++)  (0) 2022.05.30
[ 백준 ] 1562번 - 계단 수 (C++)  (0) 2022.05.29
반응형

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

 

1149번: RGB거리

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나

www.acmicpc.net

 

 

[ 문제풀이 ]

 

최대 1000개의 집이 있고, 앞의 건물과 같은 색으로 칠하면 안 된다는 조건이 있습니다. 모든 조합을 뽑아 최솟값을 결정하려면 O(2^1000)이므로 터무니없는 숫자가 나옵니다. 따라서 이 문제는 dp를 활용하여 풀어주었습니다.

 

총 3N개의 배열을 3번만 탐색하면 되므로 O(N*3*3)이라는 시간복잡도가 나옵니다.

 

앞에 칠했던 건물과 같은 색을 칠하면 안되므로 먼저 dp배열의 값들을 INF로 초기화시켜줍니다. 그리고 첫 번째 집의 색깔을 정해줍니다.

 

예를 들어 첫번째 집을 빨강으로 정한다면 그 값을 제외한 모든 값들을 INF로 초기화시키고 첫 집의 빨간 집만 색칠해줍니다.

 

그렇다면 다음 집에서 빨간색으로 집을 칠하려고 할 때 초록색과 파란색 집은 INF로 초기화 되어 있기 때문에 빨간색으로 칠하는 선택지가 사라지게 됩니다. 이러한 방법으로 첫 번째 집의 색깔을 각각 한 번씩 선택해주면 답을 얻어낼 수 있습니다.

 

[ 소스 코드 ]

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 <iostream>
#define INF 987654321
 
using namespace std;
 
int N;
int RGB[1000][3];        //비용을 저장할 배열
int dp[1000][3];        //최솟값을 저장할 배열
 
int main()
{
    cin >> N;
    int ans = INF;
 
    for (int i = 0; i < N; i++) {
        scanf("%d %d %d", &RGB[i][0], &RGB[i][1], &RGB[i][2]);
    }
 
    for (int t = 0; t < 3; t++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 3; j++) {
                if (i == t && j == 0) {
                    dp[j][i] = RGB[0][i];    //첫 집의 색을 정함
                }
                else {
                    dp[i][j] = INF;            //나머지 집은 INF로 초기화
                }
            }
        }
 
        for (int i = 1; i < N; i++) {        //각 색깔로 칠했을 때 최솟값을 dp에 저장
            dp[i][0] = min(dp[i - 1][1] + RGB[i][0], dp[i - 1][2] + RGB[i][0]);
            dp[i][1] = min(dp[i - 1][0] + RGB[i][1], dp[i - 1][2] + RGB[i][1]);
            dp[i][2] = min(dp[i - 1][0] + RGB[i][2], dp[i - 1][1] + RGB[i][2]);
        }
 
        for (int i = 0; i < 3; i++) {        //마지막에 세 집 중 가장 비용이 적은 집 ans에 저장
            if (ans > dp[N - 1][i]) {
                ans = dp[N - 1][i];
            }
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 9251번 - LCS (C++)  (0) 2022.06.02
[ 백준 ] 15686번 - 치킨 배달 (C++)  (0) 2022.06.01
[ 백준 ] 1799번 - 비숍 (C++)  (0) 2022.05.30
[ 백준 ] 1562번 - 계단 수 (C++)  (0) 2022.05.29
[ 백준 ] 10844번 - 쉬운 계단 수 (C++)  (0) 2022.05.28
반응형

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

 

1799번: 비숍

첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로

www.acmicpc.net

 

 

[ 문제풀이 ]

10초라는 시간제한 때문에 얼핏 보면 쉬워 보이는 문제이지만 10x10의 체스판을 모두 체크한다면 O(2^(100))이므로 10초라는 시간도 매우 부족합니다.

 

따라서 비숍의 특성을 이용하여 시간을 많이 줄여야합니다. 비숍은 체스판에서 서로 다른 색 위치에 있으면 서로 공격할 수 없습니다.

 

 

왜냐하면 처음 검정색 위치에 서 있던 비숍은 검은색 위만을 움직일 수 있고, 반대로 흰색 위에 있던 비숍은 흰색 위만을 움직일 수 있기 때문입니다.

 

이러한 특성을 이용하면 검은색은 검은색끼리 흰색은 흰색끼리 계산하여 O(2^(50)*2^(50))의 시간 복잡도를 가지게 되므로 10초 안에 충분히 풀 수 있습니다.

 

[ 소스 코드 ]

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <iostream>
 
using namespace std;
 
struct board {
    int num;
    int color = 0;
};
 
int N;
board arr[11][11];
int dy[4] = { -1,-1,1,1 };
int dx[4] = { -1,1,-1,1 };
int ansW;
int ansB;
 
int check(int y, int x)        //비숍을 놓을 수 있으면 1 리턴 없으면 0 리턴
{
    for (int i = 0; i < 4; i++) {
        for (int j = 1; j < N; j++) {
            int yy = y + dy[i] * j;
            int xx = x + dx[i] * j;
            if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                if (arr[yy][xx].num == 2) {
                    return 0;
                }
            }
        }
    }
 
    return 1;
}
 
void dfsW(int y, int x)        //체스판의 흰색 부분
{
    int flag = 0;
    while ((arr[y][x].num != 1 || arr[y][x].color != 0) && y<N) {
        x++;                //체스말을 놓을 수 있을 때 까지 x++
        if (x == N) {
            y++;
            x = 0;
        }
    }
    
    if (y == N) {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j].num == 2) {
                    cnt++;
                }
            }
        }
        if (ansW < cnt) {
            ansW = cnt;
        }
        return;
    }
 
    if (check(y, x)) {        //비숍을 놓을 수 있는지 없는지 체크 후
        arr[y][x].num = 2;    //말을 놓거나
    }
    else {
        flag = 1;            //놓지 못한다고 체크
    }
 
    int nx = x + 1;
    int ny = y;
    if (nx == N) {
        nx = 0;
        ny++;
    }
    dfsW(ny, nx);
 
    if (flag != 1) {        //비숍을 놓은 상황이라면
        arr[y][x].num = 1;    //원상복구
    }
    else {
        return;                //아니라면 같은 상황을 겪게 되므로 return
    }
 
    dfsW(ny, nx);
}
 
void dfsB(int y, int x)        //체스판의 검은색 부분
{
    int flag = 0;
    while ((arr[y][x].num != 1 || arr[y][x].color != 1) && y < N) {
        x++;
        if (x == N) {
            y++;
            x = 0;
        }
    }
 
    if (y == N) {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j].num == 2) {
                    cnt++;
                }
            }
        }
        if (ansB < cnt) {
            ansB = cnt;
        }
        return;
    }
 
    if (check(y, x)) {
        arr[y][x].num = 2;
    }
    else {
        flag = 1;
    }
 
    int nx = x + 1;
    int ny = y;
    if (nx == N) {
        nx = 0;
        ny++;
    }
    dfsB(ny, nx);
 
    if (flag != 1) {
        arr[y][x].num = 1;
    }
    else {
        return;
    }
 
    dfsB(ny, nx);
}
 
int main()
{
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0;j < N; j++) {
            cin >> arr[i][j].num;
            if (i % 2 == 0) {        //체스판의 검은색 부분을 1로 경신
                if (j % 2 == 1) {
                    arr[i][j].color = 1;
                }
            }
            else {
                if (j % 2 == 0) {
                    arr[i][j].color = 1;
                }
            }
        }
    }
 
    dfsW(0, 0);
    dfsB(0, 1);
 
    cout << ansW+ansB;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 15686번 - 치킨 배달 (C++)  (0) 2022.06.01
[ 백준 ] 1149번 - RGB거리 (C++)  (0) 2022.05.31
[ 백준 ] 1562번 - 계단 수 (C++)  (0) 2022.05.29
[ 백준 ] 10844번 - 쉬운 계단 수 (C++)  (0) 2022.05.28
[ 백준 ] 2407번 - 조합 (C++)  (0) 2022.05.27
반응형

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

 

1562번: 계단 수

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

https://rudalsd.tistory.com/9?category=1064612 

 

[ 백준 ] 10844번 - 쉬운 계단 수 (C++)

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net [ 문제풀이 ] 항상 dp문제를 풀 때는 표를 그려서 어떤 점화식을..

rudalsd.tistory.com

위의 문제와 많이 유사하지만 0~9까지의 모든 숫자가 들어가야 하므로 조금 더 까다로운 문제입니다.

 

위의 일반적인 계단 수를 구하는 문제를 풀어보시고 오는 것을 추천드립니다!!

 

쉬운 계단 수 문제와 유사하지만 한가지 개념만 더한다면 쉽게 풀 수 있는 문제입니다.

 

0~9까지의 모든 숫자가 들어가 있는 계단수는 0과 9에 모두 맞닿아있어야 합니다. 따라서 0에 맞닿아있으면 1번 비트에 저장하고, 9에 맞닿아있으면 2번 비트에 저장하고, 0과 9에 모두 닿아있으면 3번 비트에 저장합니다.

 

dp배열에 저장해 나가면 결국 3번 비트에 저장돼있는 모든 수를 더하면 정답을 구할 수 있습니다.

 

[ 소스 코드 ]

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 <iostream>
 
using namespace std;
 
int N;
long long dp[10][101][4];                //각 숫자가 들어갈 수 있는 개수를 저장할 배열
                                        //1 : 0과 닿음, 2 : 9와 닿음, 3 : 0, 9와 닿음
int main()
{
    cin >> N;
 
    long long cnt = 0;                    //총 개수를 저장할 변수
 
    for (int i = 1; i < 9; i++) {        //N이 1일 때 0을 제외한 각 숫자가 한번씩 들어갈 수 있으므로
        dp[i][1][0] = 1;                //모두 1로 경신
    }
 
    dp[9][1][2] = 1;
 
    for (int i = 2; i <= N; i++) {        //2자릿수 부터 돌면서
        for (int j = 0; j < 10; j++) {
            for (int k = 0; k < 4; k++) {
                if (j == 0) {            //0과 닿아있으면 k|1에 그 전의 모든 값들을 더함
                    dp[j][i][k | 1] += dp[1][i - 1][k];
                    dp[j][i][k | 1] %= 1000000000;
                }
                else if (j == 9) {        //9와 닿아있으면 k|2에 그 전의 모든 값들을 더함
                    dp[j][i][k | 2] += dp[8][i - 1][k];
                    dp[j][i][k | 2] %= 1000000000;
                }
                else {                    //아니라면 전의 값들 중 계단수들의 값들을 더함
                    dp[j][i][k] = dp[j - 1][i - 1][k] + dp[j + 1][i - 1][k];
                    dp[j][i][k] %= 1000000000;
                }
            }
        }
    }
 
    for (int i = 0; i < 10; i++) {
        cnt += dp[i][N][3];
        cnt %= 1000000000;
    }
 
    cout << cnt;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1149번 - RGB거리 (C++)  (0) 2022.05.31
[ 백준 ] 1799번 - 비숍 (C++)  (0) 2022.05.30
[ 백준 ] 10844번 - 쉬운 계단 수 (C++)  (0) 2022.05.28
[ 백준 ] 2407번 - 조합 (C++)  (0) 2022.05.27
[ 백준 ] 1509번 - 팰린드롬 분할 (C++)  (0) 2022.05.26

+ Recent posts

티스토리툴바