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

 

1577번: 도로의 개수

첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 100보다 작거나 같은

www.acmicpc.net

(0, 0)에서 출발하여 (N, M)에 도착할 수 있는 경우의 수를 구하는문제입니다.

다만 이 문제는 공사중이어서 갈 수 없는 길이 존재하는데 거리는 항상 1이므로 set으로 관리하였습니다.

 

(a, b), (c, d) 형식으로 입력이 주어지면 (a, b)에서 (c, d)로 가는 길, (c, d)에서 (a, b)로 가는 길 모두 체크하였습니다.

로직은 dfs+dp으로 구성하였고, 이동은 최단거리로만 이동하기 때문에 뒤로는 가지 않아야합니다.

 

이 문제의 답은 long long 범위라고 명시되어 있으므로 long long으로 구해줍니다.

 

 

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
#include <iostream>
#include <set>
#include <cstring>
using namespace std;
typedef long long ll;
 
set<pair<int, int> > s[101][101];
ll dp[101][101];
int list[101][101];
int direct[2][2] = { {0,1},{1,0} };
int N, M, K;
 
ll func(int x, int y) {
    if (x == N && y == M) return 1;
 
    ll &ret = dp[x][y];
    if (ret != -1) return ret;
    ret = 0;
 
    for (int i = 0; i < 2; i++) {
        int nx = x + direct[i][0];
        int ny = y + direct[i][1];
 
        if (nx > N || ny > M) continue;
        if (s[x][y].find({ nx,ny }) != s[x][y].end()) continue;
 
        ret += func(nx, ny);
    }
 
    return ret;
}
 
void input() {
    int sx, sy, ex, ey;
    cin >> N >> M >> K;
    while (K--) {
        cin >> sx >> sy >> ex >> ey;
        s[sx][sy].insert({ ex,ey });
        s[ex][ey].insert({ sx,sy });
    }
    memset(dp, -1, sizeof(dp));
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    cout << func(0, 0) << '\n';
    
    return 0;
}
 cs

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

boj 14700 넴모넴모 (Hard)  (0) 2021.06.22
boj 1311 할 일 정하기 1  (0) 2021.06.21
boj 4781 사탕 가게  (0) 2021.06.19
boj 2186 문자판  (0) 2021.06.19
boj 13325 이진 트리  (0) 2021.06.18

www.acmicpc.net/problem/15663

 

15663번: N과 M (9)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

N과M 9번째 문제입니다.

 

다른 문제들과 다른 점은 배열에 중복되는 숫자가 포함되어 주어진다는 것입니다.

 

결과를 출력하였을 때 중복 값을 제외하고 출력해야해서 Set에 ArrayList를 넣어 중복체크를 하였습니다.

 

수열은 오름차순으로 이루어져야한다는 말이 없으니 0번 인덱스부터 계속 돌려주시면 됩니다.

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static ArrayList<Integer> list, ans;
    static int N, M;
    static boolean visit[];
    static Set<ArrayList<Integer>> s = new HashSet<>();
 
    static void dfs(int cnt) {
        if (cnt == M) {
            if (s.contains(ans))
                return;
 
            s.add(ans);
            for (int i = 0; i < ans.size(); i++) {
                sb.append(ans.get(i) + " ");
            }
            sb.append("\n");
            return;
        }
 
        for (int i = 0; i < N; i++) {
            if (visit[i])
                continue;
 
            int x = list.get(i);
 
            visit[i] = true;
            ans.add(x);
            dfs(cnt + 1);
            ans.remove(cnt);
            visit[i] = false;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new ArrayList<>();
        ans = new ArrayList<>();
        visit = new boolean[N];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            list.add(Integer.parseInt(st.nextToken()));
        }
        Collections.sort(list);
    }
 
    public static void main(String[] args) throws Exception {
        input();
        dfs(0);
        System.out.println(sb.toString());
    }
}
 cs

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

boj 15665 N과 M (11)  (0) 2021.01.30
boj 15664 N과 M (10)  (0) 2021.01.30
boj 15657 N과 M (8)  (0) 2021.01.27
boj 15656 N과 M (7)  (0) 2021.01.27
boj 15655 N과 M (6)  (0) 2021.01.27

+ Recent posts

티스토리툴바