반응형

* 핵심 개념

고려해야 할 사항은 크게 두가지다.

1. 물고기가 같은 거리에 있는 경우 위에 있고, 왼쪽에 있는 물고기를 먹는다. 

다른 방법도 존재하지만 우선순위 큐를 사용하여 처리하였다. (148ms)

먹이를 찾았을 때 큐에 남은 점들을 다시 확인해서 비교한다. (80ms)

2. 물고기를 먹고 나서 상어 크기가 증가하는 지 확인해야 한다.

하나 주의해야 할 점은 상어의 위치를 받고 map을 0으로 변경해주는 작업도 필요하다.


요약하면, 

상어 위치 확인  >> 물고기 탐색(BFS) >> 찾은 물고기 우선순위 큐에 저장 >> 우선순위 큐의 맨 앞 물고기 선택 >> 상어 위치 변경 및 상어 크기 증가여부 확인

상어 위치 확인 >> 물고기 탐색(BFS) >> 물고기 찾으면 남아있는 큐 탐색 >> 최적의 물고기 위치 확인 >> 상어 위치 변경 및 상어 크기 증가 여부 확인

위 순서대로 진행하며 BFS가 끝낫는데 큐의 크기가 0이라면 먹을 수 있는 물고기가 없다는 뜻이므로 움직인 거리를 출력하면 된다.

* 문제

문제

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

  • 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
  • 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
  • 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
    • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최소값이다.
    • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

  • 0: 빈 칸
  • 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
  • 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

* 소스 코드

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
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int[] dx = {-1, 0, 0, 1};
    public static int[] dy = {0, -1, 1, 0};
    public static int n, eating = 0;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        int[][] map = new int[n][n];
        Queue<Shark> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
                if (map[i][j] == 9) {
                    q.add(new Shark(i, j, 2, 0));
                    map[i][j] = 0;
                }
            }
        }
 
        int ans = 0;
        boolean[][] visited = new boolean[n][n];
        while (!q.isEmpty()) {
            Shark shark = q.poll();
            if (!visited[shark.x][shark.y]) {
                visited[shark.x][shark.y] = true;
                if (map[shark.x][shark.y] != 0 && map[shark.x][shark.y] < shark.power) {  //상어가 먹이를 찾으면
                    Shark curr = shark;
                    //거리 > 높이 > 왼쪽 순서로 먹기 위해 남은 Queue 탐색
                    while (!q.isEmpty()) {
                        shark = q.poll();
                        if (map[shark.x][shark.y] != 0 && map[shark.x][shark.y] < shark.power) {
                            if (curr.cost == shark.cost) {
                                if (curr.x > shark.x) {
                                    curr = shark;
                                } else if (curr.x == shark.x && curr.y > shark.y) {
                                    curr = shark;
                                }
                            } else if (curr.cost > shark.cost) {
                                curr = shark;
                            }
                        }
                    }
                    map[curr.x][curr.y] = 0;
                    eating++;
                    ans += curr.cost;
                    int flag = 0;
                    if (eating == curr.power) {        //상어가 성장할 수 있으면
                        flag = 1;
                        eating = 0;
                    }
                    q.clear();
                    q.add(new Shark(curr.x, curr.y, curr.power + flag, 0));
                    visited = new boolean[n][n];
                    continue;
                }
                for (int i = 0; i < 4; i++) {
                    int nx = shark.x + dx[i];
                    int ny = shark.y + dy[i];
                    if (nx >= 0 && nx < n && ny >= 0 && ny < n && map[nx][ny] <= shark.power && !visited[nx][ny]) {
                        q.add(new Shark(nx, ny, shark.power, shark.cost + 1));
                    }
                }
            }
        }
        System.out.println(ans);
    }
 
    public static class Shark {
        int x, y, power, cost;
 
        public Shark(int x, int y, int power, int cost) {
            this.x = x;
            this.y = y;
            this.power = power;
            this.cost = cost;
        }
    }
}
cs


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

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

[Algorithm] 백준/16234 :: 인구 이동  (0) 2019.03.24
[Algorithm] 백준/13460 :: 구슬 탈출 2  (0) 2019.03.10
[Algorithm] 백준/14502 :: 연구소  (0) 2019.03.02
[Algorithm] 백준/14501 :: 퇴사  (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
반응형

* 핵심

삼성 기출문제중 난이도가 낮은 편으로 범위가 작아서 백트레킹과 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
반응형

* 핵심

Backtracking 문제로 접근하여 n명이 있을 때, n/2 명의 팀을 하나의 팀으로 선정하는 작업을 우선 


* 문제

문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

i\j1234
1 123
24 56
371 2
4345 

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

  • 스타트 팀: S12 + S21 = 1 + 4 = 5
  • 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

  • 스타트 팀: S13 + S31 = 2 + 7 = 9
  • 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.


* 소스 코드

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
import java.io.*;
import java.util.*;
 
public class Main {
    public static int n;
    public static int min = Integer.MAX_VALUE;
    public static int[][] map;
    public static boolean[] visited;        //방문
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
 
        n = Integer.parseInt(stk.nextToken());
        map = new int[n][n];
        visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
            }
        }
        backtracking(0, 0);
        System.out.println(min);
    }
 
    public static void backtracking(int start, int depth) {
        if (n / 2 == depth) {
            int t1 = 0, t2 = 0;
            for (int i = 0; i < n; i++) {
                for (int j = i+1; j < n; j++) {
                    if (visited[i] && visited[j]) {
                        t1 += map[i][j] + map[j][i];
                    }
                    if (!(visited[i] || visited[j])) {
                        t2 += map[i][j] + map[j][i];
                    }
                }
            }
            min = Math.min(min, Math.abs(t1 - t2));
            return;
        } else {
            for (int i = start; i < n; i++) {
                if (!visited[i]) {
                    visited[i] = true;
                    backtracking(i, depth + 1);
                    visited[i] = false;
                }
            }
        }
    }
}
cs


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

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

[Algorithm] 백준/16236 :: 아기 상어  (0) 2019.03.10
[Algorithm] 백준/14502 :: 연구소  (0) 2019.03.02
[Algorithm] 백준/14501 :: 퇴사  (0) 2019.02.12
[Algorithm] 백준/14888 :: 연산자 끼워넣기  (0) 2019.01.04
반응형

* 핵심

Backtracking으로 문제 접근, 계산 전에 연산자의 수를 하나 뺏다가 다시 추가하는 작업 필수


* 문제

문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

  • 1+2+3-4×5÷6
  • 1÷2+3+4-5×6
  • 1+2÷3×4-5+6
  • 1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

  • 1+2+3-4×5÷6 = 1
  • 1÷2+3+4-5×6 = 12
  • 1+2÷3×4-5+6 = 5
  • 1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 최댓값과 최솟값은 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 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
import java.io.*;
import java.util.*;
 
public class Main {
    public static int n;
    public static int[] num;
    public static int[] op = new int[4];
    public static int min = 1000000000;
    public static int max = -1000000000;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
 
        n = Integer.parseInt(stk.nextToken());
        num = new int[n];
        stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            num[i] = Integer.parseInt(stk.nextToken());
        }
        stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {
            op[i] = Integer.parseInt(stk.nextToken());
        }
        backtracking(num[0], 1);
        System.out.println(max);
        System.out.println(min);
    }
 
    public static void backtracking(int res, int cnt) {
        if (cnt == n) {
            min = Math.min(min, res);
            max = Math.max(max, res);
            return;
        } else {
            for (int i = 0; i < 4; i++) {
                if (op[i] != 0) {
                    op[i]--;        //해당 연산자 개수 하나 감소
                    if (i == 0) backtracking(res + num[cnt], cnt + 1);
                    if (i == 1) backtracking(res - num[cnt], cnt + 1);
                    if (i == 2) backtracking(res * num[cnt], cnt + 1);
                    if (i == 3) backtracking(res / num[cnt], cnt + 1);
                    op[i]++;        //해당 연산자 개수 
                }
            }
        }
    }
}
cs


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

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

[Algorithm] 백준/16236 :: 아기 상어  (0) 2019.03.10
[Algorithm] 백준/14502 :: 연구소  (0) 2019.03.02
[Algorithm] 백준/14501 :: 퇴사  (0) 2019.02.12
[Algorithm] 백준/14889 :: 스타트와 링크  (0) 2019.01.04

티스토리툴바