반응형

* 핵심

우선순위 큐를 사용해서 끝나는 순서가 빠른 순서대로 정렬


* 문제

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 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
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Info> pq = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine());
            pq.add(new Info(Integer.parseInt(stk.nextToken()), Integer.parseInt(stk.nextToken())));
        }
        int end = 0;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            Info o = pq.poll();
            if (o.start >= end) {   //이전 끝난 시간보다 새로 시작하는 회의 시간이 크거나 같으면
                end = o.end;
                cnt++;
            }
        }
        System.out.println(cnt);
    }
 
    public static class Info implements Comparable<Info> {
        int start, end;
 
        public Info(int start, int end) {
            this.start = start;
            this.end = end;
        }
 
        @Override
        public int compareTo(Info o) {
            if (end == o.end) return start - o.start;   //같은 시간에 끝나면 Start 오름 차순
            return end - o.end;     //끝나는 순서 오름차순 정렬
        }
    }
}
cs


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

'∙Algorithm' 카테고리의 다른 글

[Algorithm] 백준/1655 :: 가운데를 말해요  (0) 2019.04.21
[Algorithm] 백준/1946 :: 신입 사원  (0) 2019.03.24
[Algorithm] 백준/16985 :: Maaaaaaaaaze  (0) 2019.03.01
[Algorithm] 백준/11057 :: 오르막 수  (0) 2019.02.12
반응형

* 핵심

어제 올린 백준/16985 :: Maaaaaaaaaze 와 비슷하지만 조금 쉬운 문제이다.

이 문제 또한 3단계로 나누어서 해결할 수 있다.

1. 입력받은 map에서 0인 좌표중에서 3개를 선택하는 함수 nCr >> 벽 3곳 선정

2. BFS를 통해서 바이러스 퍼트리기

3. 안전지역 비교 함수


* 문제 

문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 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
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
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int[][] map;
    public static ArrayList<Point> virusPos = new ArrayList<>();    //바이러스의 좌표를 저장하는 ArrayList
    public static int[] dx = {1, -1, 0, 0};
    public static int[] dy = {0, 0, 1, -1};
    public static int n, m;
    public static int ans = 0;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        stk = new StringTokenizer(br.readLine());
        n = Integer.parseInt(stk.nextToken());
        m = Integer.parseInt(stk.nextToken());
        map = new int[n][m];
        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
                if (map[i][j] == 2) virusPos.add(new Point(i, j));
            }
        }
 
        nCr(0, new boolean[n][m]);
        System.out.println(ans);
    }
 
    //0의 개수들 중에서 3개의 점에 벽을 세우는 경우의 수
    public static void nCr(int cnt, boolean[][] visited) {
        if (cnt == 3) {
            int[][] nmap = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (!visited[i][j]) nmap[i][j] = map[i][j];
                    else nmap[i][j] = 1;
                }
            }
            bfs(nmap);
            return;
        }
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m; y++) {
                if (map[x][y] == 0 && !visited[x][y]) {
                    visited[x][y] = true;
                    nCr(cnt + 1, visited);
                    visited[x][y] = false;
                }
            }
        }
        return;
    }
 
    //bfs를 이용해서 바이러스가 주위로 퍼져나감
    public static void bfs(int[][] nmap) {
        Queue<Point> q = new LinkedList<>();
        boolean[][] visited = new boolean[n][m];
        for (int i = 0; i < virusPos.size(); i++) {
            q.add(virusPos.get(i));     //바이러스의 좌표들을 큐에 저장
        }
        while (!q.isEmpty()) {
            Point p = q.poll();
            if (!visited[p.x][p.y] && nmap[p.x][p.y] != 1) {
                visited[p.x][p.y] = true;
                nmap[p.x][p.y] = 2;
                for (int i = 0; i < 4; i++) {
                    int nx = p.x + dx[i];
                    int ny = p.y + dy[i];
                    if (check(nx, ny) && !visited[nx][ny] && nmap[nx][ny] != 1) {
                        q.add(new Point(nx, ny));
                    }
                }
            }
        }
        ans = Math.max(ans, getSafeCnt(nmap));
    }
 
    //안전지역 숫자를 세는 함수
    public static int getSafeCnt(int[][] nmap) {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (nmap[i][j] == 0) cnt++;
            }
        }
        return cnt;
    }
 
    public static boolean check(int x, int y) {
        if (x >= 0 && x < n && y >= 0 && y < m) return true;
        return false;
    }
 
    public static class Point {
        int x, y;
 
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
cs


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

'∙Algorithm > 삼성 SW 역량테스트' 카테고리의 다른 글

[Algorithm] 백준/13460 :: 구슬 탈출 2  (0) 2019.03.10
[Algorithm] 백준/16236 :: 아기 상어  (0) 2019.03.10
[Algorithm] 백준/14501 :: 퇴사  (0) 2019.02.12
[Algorithm] 백준/14889 :: 스타트와 링크  (0) 2019.01.04
반응형

* 핵심

문제를 하루종일 삽질하면서 풀었다.

첫번째 실수는 문제를 이해를 잘못해서 각 미로를 nCr로 조합한다는 경우를 생각하지 못했고, 

두번째 실수는 visited를 매번 초기화하지 않아서 한바퀴밖에 돌지않는 경우가 발생했다.


문제를 뜯어보면 3가지 역할로 분리할 수 있다.

1. nCr 함수 : 판을 쌓는 순서를 참가자가 자유롭게 정할 수 있으므로 5!의 경우의 수가 발생

2. Rotation(DFS) 함수 : 판을 돌리는 경우의 수는 총 4가지이므로 4^5(판의 개수) 의 경우의 수 발생 >> DFS로 경우의 수 찾기

3. BFS 함수 : Rotaion으로 받은 map을 가지고 0,0,0에서 4,4,4로 가는 경우의 수를 찾는 함수

문제를 위처럼 3단계로 나누고 실수없이 구현하면 금방 풀 수 있는 문제였다.

특히, 자바는 파라미터가 Call by Reference이기 때문에 DFS 함수를 호출하고 다시 값을 변경해주는 것 또한 잊지말아야 한다.


* 문제

문제

평화롭게 문제를 경작하며 생활하는 BOJ 마을 사람들은 더 이상 2차원 미로에 흥미를 느끼지 않는다. 2차원 미로는 너무나 쉽게 탈출이 가능하기 때문이다. 미로를 이 세상 그 누구보다 사랑하는 준현이는 이런 상황을 매우 안타깝게 여겨 아주 큰 상금을 걸고 BOJ 마을 사람들의 관심을 확 끌 수 있는 3차원 미로 탈출 대회를 개최하기로 했다.

대회의 규칙은 아래와 같다.

  • 5×5 크기의 판이 5개 주어진다. 이중 일부 칸은 참가자가 들어갈 수 있고 일부 칸은 참가자가 들어갈 수 없다. 그림에서 하얀 칸은 참가자가 들어갈 수 있는 칸을, 검은 칸은 참가자가 들어갈 수 없는 칸을 의미한다.

  • 참가자는 주어진 판들을 시계 방향, 혹은 반시계 방향으로 자유롭게 회전할 수 있다. 그러나 판을 뒤집을 수는 없다.

  • 회전을 완료한 후 참가자는 판 5개를 쌓는다. 판을 쌓는 순서는 참가자가 자유롭게 정할 수 있다. 이렇게 판 5개를 쌓아 만들어진 5×5×5 크기의 큐브가 바로 참가자를 위한 미로이다. 이 때 큐브의 입구는 정육면체에서 참가자가 임의로 선택한 꼭짓점에 위치한 칸이고 출구는 입구와 면을 공유하지 않는 꼭짓점에 위치한 칸이다.

  • 참가자는 현재 위치한 칸에서 면으로 인접한 칸이 참가자가 들어갈 수 있는 칸인 경우 그 칸으로 이동할 수 있다.
  • 참가자 중에서 본인이 설계한 미로를 가장 적은 이동 횟수로 탈출한 사람이 우승한다. 만약 미로의 입구 혹은 출구가 막혀있거나, 입구에서 출구에 도달할 수 있는 방법이 존재하지 않을 경우에는 탈출이 불가능한 것으로 간주한다.

이 대회에서 우승하기 위해서는 미로를 잘 빠져나올 수 있기 위한 담력 증진과 체력 훈련, 그리고 적절한 운이 제일 중요하지만, 가장 적은 이동 횟수로 출구에 도달할 수 있게끔 미로를 만드는 능력 또한 없어서는 안된다. 주어진 판에서 가장 적은 이동 횟수로 출구에 도달할 수 있게끔 미로를 만들었을 때 몇 번 이동을 해야하는지 구해보자. 

입력

첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 의미한다.

출력

첫째 줄에 주어진 판으로 설계된 미로를 탈출하는 가장 적은 이동 횟수를 출력한다. 단, 어떻게 설계하더라도 탈출이 불가능할 경우에는 -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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int[][][] map = new int[5][5][5];
    public static boolean[][][] visited = new boolean[5][5][5];
    public static int[] p = {0, 0, 0, 0, 0};        //nCr로 순서를 정할 때 idx를 저장하는 배열
    public static int[] dx = {1, -1, 0, 0, 0, 0};
    public static int[] dy = {0, 0, 1, -1, 0, 0};
    public static int[] dh = {0, 0, 0, 0, 1, -1};
    public static int ans = Integer.MAX_VALUE;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < 5; i++) {                //높이
            for (int j = 0; j < 5; j++) {            //가로
                stk = new StringTokenizer(br.readLine());
                for (int k = 0; k < 5; k++) {        //세로
                    map[i][j][k] = Integer.parseInt(stk.nextToken());
                }
            }
        }
        nCr(0, new boolean[5]);
        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
    }
 
    //참가자가 5개의 판을 쌓는 5!의 경우의 수
    public static void nCr(int cnt, boolean[] visited) {
        if (cnt == 5) {        //경우의 수를 찾았을때마다 만든 배열을 가지고 Backtracking 함수 호출
            int[][][] nmap = new int[5][5][5];
            for (int i = 0; i < 5; i++) {
                int idx = p[i];
                for (int x = 0; x < 5; x++) {
                    for (int y = 0; y < 5; y++) {
                        nmap[i][x][y] = map[idx][x][y];
                    }
                }
            }
            Backtracking(0, new int[5][5][5], nmap);
            return;
        }
        for (int i = 0; i < 5; i++) {
            if (!visited[i]) {
                visited[i] = true;
                p[i] = cnt;
                nCr(cnt + 1, visited);
                p[i] = 0;
                visited[i] = false;
            }
        }
        return;
    }
 
    //dfs를 이용하여 각 높이별 회전할 때의 저장배열
    public static void Backtracking(int height, int[][][] nmap, int[][][] map) {
        if (height == 5) {        //배치한 판을 회전시킨 경우의 수마다 bfs 
            if (nmap[0][0][0] == 1 && nmap[4][4][4] == 1) {
                int tmp = bfs(nmap);
                if (tmp != -1) ans = Math.min(ans, tmp);
            }
            return;
        }
        for (int cnt = 1; cnt <= 4; cnt++) {     //반시계 돌리는 횟수
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    if (map[height][i][j] == 1) {
                        switch (cnt) {
                            case 1:
                                nmap[height][j][4 - i] = 1;
                                break;
                            case 2:
                                nmap[height][4 - i][4 - j] = 1;
                                break;
                            case 3:
                                nmap[height][4 - j][i] = 1;
                                break;
                            case 4:
                                nmap[height][i][j] = 1;
                                break;
                        }
                    }
                }
            }
            Backtracking(height + 1, nmap, map);
            nmap[height] = new int[5][5];
        }
        return;
    }
 
    //bfs를 이용해서 저장된 nmap을 가지고 정점가능횟수 찾는 횟수
    public static int bfs(int[][][] nmap) {
        Queue<Point> q = new LinkedList<>();
        visited = new boolean[5][5][5];
        q.add(new Point(0, 0, 0, 0));
        while (!q.isEmpty()) {
            Point p = q.poll();
            if (p.height == 4 && p.x == 4 && p.y == 4) return p.cnt;
            if (!visited[p.height][p.x][p.y]) {
                visited[p.height][p.x][p.y] = true;
                for (int k = 0; k < 6; k++) {
                    int nh = p.height + dh[k];
                    int nx = p.x + dx[k];
                    int ny = p.y + dy[k];
                    if (check(nh, nx, ny) && nmap[nh][nx][ny] == 1 && !visited[nh][nx][ny]) {
                        q.add(new Point(nh, nx, ny, p.cnt + 1));
                    }
                }
            }
        }
        return -1;
    }
 
    public static boolean check(int h, int x, int y) {
        if (h >= 0 && h < 5 && x >= 0 && x < 5 && y >= 0 && y < 5) return true;
        return false;
    }
 
    public static class Point {
        int height, x, y, cnt;
 
        public Point(int height, int x, int y, int cnt) {
            this.height = height;
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
}
cs


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

'∙Algorithm' 카테고리의 다른 글

[Algorithm] 백준/1946 :: 신입 사원  (0) 2019.03.24
[Algorithm] 백준/1931 :: 회의실배정  (0) 2019.03.07
[Algorithm] 백준/11057 :: 오르막 수  (0) 2019.02.12
[Algorithm] 백준/5557 :: 1학년  (0) 2019.02.12
반응형

* 핵심

삼성 기출문제중 난이도가 낮은 편으로 범위가 작아서 백트레킹과 DP로 풀 수 있는 문제다.

DP를 이용하여 푸는 경우 중간에 계속 Max값을 저장해줘야 한다.


* 문제

문제

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

 1일2일3일4일5일6일7일
Ti3511242
Pi102010201540200

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti≤ 5, 1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.


* 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[21];     //i번째 날이 끝나면 받는 최대 비용
        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(stk.nextToken());
            int p = Integer.parseInt(stk.nextToken());
            dp[i + 1] = Math.max(dp[i], dp[i + 1]);
            dp[i + t] = Math.max(dp[i + t], dp[i] + p);
        }
        System.out.println(dp[n]);
    }
}
cs


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

'∙Algorithm > 삼성 SW 역량테스트' 카테고리의 다른 글

[Algorithm] 백준/16236 :: 아기 상어  (0) 2019.03.10
[Algorithm] 백준/14502 :: 연구소  (0) 2019.03.02
[Algorithm] 백준/14889 :: 스타트와 링크  (0) 2019.01.04
[Algorithm] 백준/14888 :: 연산자 끼워넣기  (0) 2019.01.04
반응형

* 핵심

오르막 수라면 마지막 수보다 다음 숫자가 커지면 안된다.

dp[i][j]는 i번째 자리수가 j일 때의 만들수 있는 경우의 수로 잡으면 

dp[i][j] += dp[i-1][j~10]이 될 것이다.


* 문제

문제

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.


* 소스 코드

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
import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[][] dp = new long[n + 1][10];    //i번째 순서의 마지막 숫자가 j일때의 경우의 수
        for (int i = 0; i < 10; i++) {
            dp[1][i] = 1;
        }
        for (int idx = 2; idx <= n; idx++) {
            for (int cnt = 0; cnt < 10; cnt++) {
                for (int i = cnt; i < 10; i++) {
                    dp[idx][cnt] += dp[idx - 1][i];
                    dp[idx][cnt] %= 10007;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < 10; i++) {
            ans += dp[n][i];
            ans %= 10007;
        }
        System.out.println(ans);
    }
}
cs


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

'∙Algorithm' 카테고리의 다른 글

[Algorithm] 백준/1931 :: 회의실배정  (0) 2019.03.07
[Algorithm] 백준/16985 :: Maaaaaaaaaze  (0) 2019.03.01
[Algorithm] 백준/5557 :: 1학년  (0) 2019.02.12
[Algorithm] 백준/1010 :: 다리 놓기  (0) 2019.01.28
반응형

*핵심

처음에는 Backtracking으로 접근했다가 n의 범위때문에 시간 초과가 발생했다.

그렇다면 DP로 해결할 수 있는 문제인데, DP에 어떤 값을 저장할 것인지가 문제이다.

dp[i][j] = i번째 순서에 j를 만들 수 있는 경우의 수를 저장했다.


* 문제

문제

상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다.

상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다. 예를 들어, "8+3+2-4-8-7+2+4+0+8=8"은 올바른 등식이지만, 8+3+2-4-8-7이 음수이기 때문에, 상근이가 만들 수 없는 등식이다.

숫자가 주어졌을 때, 상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 숫자의 개수 N이 주어진다. (3 ≤ N ≤ 100) 둘째 줄에는 0 이상 9 이하의 정수 N개가 공백으로 구분해 주어진다.

출력

첫째 줄에 상근이가 만들 수 있는 올바른 등식의 개수를 출력한다. 이 값은 263-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
import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer stk = new StringTokenizer(br.readLine());
        int[] num = new int[n + 1];
        long[][] dp = new long[n + 1][21]; //i번째 순서에 만들어진 j값의 경우의 
        for (int i = 1; i <= n; i++) {
            num[i] = Integer.parseInt(stk.nextToken());
        }
 
        dp[1][num[1]] = 1;
        for (int idx = 2; idx <= n - 1; idx++) {    //순서
            for (int cnt = 0; cnt <= 20; cnt++) {   //만들 수 있는 숫자
                if (dp[idx - 1][cnt] != 0) {        //이전 순서에서 만들 수 있었다면
                    if (cnt + num[idx] <= 20) {
                        dp[idx][cnt + num[idx]] += dp[idx - 1][cnt];
                    }
                    if (cnt - num[idx] >= 0) {
                        dp[idx][cnt - num[idx]] += dp[idx - 1][cnt];
                    }
                }
            }
        }
        System.out.println(dp[n - 1][num[n]]);
    }
}
cs


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

'∙Algorithm' 카테고리의 다른 글

[Algorithm] 백준/16985 :: Maaaaaaaaaze  (0) 2019.03.01
[Algorithm] 백준/11057 :: 오르막 수  (0) 2019.02.12
[Algorithm] 백준/1010 :: 다리 놓기  (0) 2019.01.28
[Algorithm] 백준/5568 :: 카드 놓기  (0) 2019.01.28
반응형

* 핵심

nCr = (n-1)C(r-1) + (n-1)Cr 공식을 이해한다.

1을 선택했을 때의 경우의 수 (n-1)C(r-1), 1을 선택하지 않았을 때의 경우의 수 (n-1)Cr

* 문제

문제

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

출력

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

* 소스 코드

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
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuffer sb = new StringBuffer();
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        stk = new StringTokenizer(br.readLine());
 
        int t = Integer.parseInt(stk.nextToken());
        int[][] dp = new int[31][31];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp.length; j++) {
                if (i == j) {
                    dp[i][j] = 1;
                    dp[i][0] = 1;
                }
            }
        }
        while (t-- > 0) {
            stk = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(stk.nextToken());
            int m = Integer.parseInt(stk.nextToken());
 
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= m; j++) {
                    if (dp[i][j] == 0) {
                        dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
                    }
                }
            }
            sb.append(dp[m][n] + "\n");
        }
        System.out.println(sb);
    }
}
cs


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

'∙Algorithm' 카테고리의 다른 글

[Algorithm] 백준/11057 :: 오르막 수  (0) 2019.02.12
[Algorithm] 백준/5557 :: 1학년  (0) 2019.02.12
[Algorithm] 백준/5568 :: 카드 놓기  (0) 2019.01.28
[Algorithm] 백준/5639 :: 이진 검색 트리  (0) 2019.01.22
반응형

* 핵심

숫자를 보는게 아닌 각 입력값의 idx를 순서를 구분해서 뽑는 과정이다.

1234~1432, 2134~2431 ... 순서를 전부 확인하는 Backtracking 코드를 구현한다.

* 문제

문제

상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까?

예를 들어, 카드가 5장 있고, 카드에 쓰여 있는 수가 1, 2, 3, 13, 21라고 하자. 여기서 3장을 선택해서 정수를 만들려고 한다. 2, 1, 13을 순서대로 나열하면 정수 2113을 만들 수 있다. 또, 21, 1, 3을 순서대로 나열하면 2113을 만들 수 있다. 이렇게 한 정수를 만드는 조합이 여러 가지 일 수 있다.

n장의 카드에 적힌 숫자가 주어졌을 때, 그 중에서 k개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이, 둘째 줄에 k가 주어진다. 셋째 줄부터 n개 줄에는 카드에 적혀있는 수가 주어진다.

출력

첫째 줄에 상근이가 만들 수 있는 정수의 개수를 출력한다.

* 소스 코드

import java.io.*;
import java.util.*;
public class Main {
	public static StringTokenizer stk;
	public static StringBuffer sb = new StringBuffer();
	public static HashSet<String> hs = new HashSet<>();
	public static boolean[] visited;
	public static String[] card;
	public static int cnt = 0, n, k;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		k = Integer.parseInt(br.readLine());
		card = new String[n + 1];
		visited = new boolean[n + 1];
		for (int i = 1; i <= n; i++) {
			card[i] = br.readLine();
		}
		dfs(k, 1, "");
		System.out.println(hs.size());
	}
	public static void dfs(int k, int idx, String s) {
		if (k == 0) {
			hs.add(s);
			return;
		}
		if (idx > n) {
			return;
		}
		for (int i = 1; i <= n; i++) {
			if (!visited[i]) {
				visited[i] = true;
				dfs(k - 1, i, s + card[i]);
				visited[i] = false;
			}
		}
	}
}


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

'∙Algorithm' 카테고리의 다른 글

[Algorithm] 백준/5557 :: 1학년  (0) 2019.02.12
[Algorithm] 백준/1010 :: 다리 놓기  (0) 2019.01.28
[Algorithm] 백준/5639 :: 이진 검색 트리  (0) 2019.01.22
[Algorithm] 백준/1275 :: 커피숍2  (0) 2019.01.22

티스토리툴바