2017 상반기 삼성 SW 기출문제.

시험장에서 못 풀었는데..

예외 생각하는 게 아직 힘들다. 공부 필요.


이 문제에서 중요한 것 : ㅓㅏㅗㅜ 처리

사용한 처리 방법 : 상하좌우 다 더한 뒤에 제일 작은 값 빼줌(cross 함수)


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
import java.util.Scanner;
import java.io.FileInputStream;
 
class Main {
    static int n;
    static int m;
    static int max = 0;
    static int map[][];
    static int visited[][];
    static int blocks[] = new int[4];
    
    static int dx[] = { 1, -1, 0, 0 };
    static int dy[] = { 0, 0, 1, -1 };
 
    public static void main(String args[]) throws Exception {
        // Scanner sc = new Scanner(new FileInputStream("sample_input.txt"));
 
        Scanner sc = new Scanner(System.in);
 
        n = sc.nextInt();
        m = sc.nextInt();
        map = new int[n][m];
        visited = new int[n][m];
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = sc.nextInt();
            }
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                DFS(i, j, 0);
                cross(i, j);
            }
        }
 
        System.out.println(max);
 
    } // main
 
    static void DFS(int curr_x, int curr_y, int depth) {
        if (depth == 4) {
            int sum = 0;
 
            for (int i = 0; i < 4; i++) {
                sum += blocks[i];
            }
 
            if (sum > max)
                max = sum;
 
            return;
        }
 
        visited[curr_x][curr_y] = 1;
        blocks[depth] = map[curr_x][curr_y];
 
        for (int i = 0; i < 4; i++) {
            int next_x = curr_x + dx[i];
            int next_y = curr_y + dy[i];
 
            if (next_x >= 0 && next_y >= 0 && next_x < n && next_y < m && visited[next_x][next_y] == 0) {
                DFS(next_x, next_y, depth + 1);
            }
        }
 
        visited[curr_x][curr_y] = 0;
 
    } // DFS
 
    static void cross(int curr_x, int curr_y) {
        int sum = map[curr_x][curr_y];
        int min = 99999;
        int cnt = 0;
 
        for (int i = 0; i < 4; i++) {
            int next_x = curr_x + dx[i];
            int next_y = curr_y + dy[i];
 
            if (next_x >= 0 && next_y >= 0 && next_x < n && next_y < m) {
                sum += map[next_x][next_y];
                cnt++;
 
                if (min > map[next_x][next_y])
                    min = map[next_x][next_y];
            }
        }
 
        if (cnt == 4)
            sum -= min;
 
        if (sum > max)
            max = sum;
 
    }
 
}
cs

2. 수들을 합해가고 빼가면서 계산하는 방법

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
import java.util.Scanner;
import java.io.FileInputStream;
 
class Main {
    static int n;
    static int m;
    static int max = 0;
    static int sum = 0;
    static int map[][];
    static int visited[][];
    static int dx[] = { 1, -1, 0, 0 };
    static int dy[] = { 0, 0, 1, -1 };
 
    public static void main(String args[]) throws Exception {
        // Scanner sc = new Scanner(new FileInputStream("sample_input.txt"));
 
        Scanner sc = new Scanner(System.in);
 
        n = sc.nextInt();
        m = sc.nextInt();
        map = new int[n][m];
        visited = new int[n][m];
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = sc.nextInt();
            }
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                DFS(i, j, 0);
                sum = 0;
                cross(i, j);
                sum = 0;
            }
        }
 
        System.out.println(max);
 
    } // main
 
    static void DFS(int curr_x, int curr_y, int depth) {
        if (depth == 4) {
            if(sum > max)
                max = sum;
            
            return;
        }
 
        visited[curr_x][curr_y] = 1;
        sum += map[curr_x][curr_y];
 
        for (int i = 0; i < 4; i++) {
            int next_x = curr_x + dx[i];
            int next_y = curr_y + dy[i];
 
            if (next_x >= 0 && next_y >= 0 && next_x < n && next_y < m && visited[next_x][next_y] == 0) {
                DFS(next_x, next_y, depth + 1);
            }
        }
 
        visited[curr_x][curr_y] = 0;
        sum -= map[curr_x][curr_y];
 
    } // DFS
 
    static void cross(int curr_x, int curr_y) {
        sum = map[curr_x][curr_y];
        int min = 99999;
        int cnt = 0;
 
        for (int i = 0; i < 4; i++) {
            int next_x = curr_x + dx[i];
            int next_y = curr_y + dy[i];
 
            if (next_x >= 0 && next_y >= 0 && next_x < n && next_y < m) {
                sum += map[next_x][next_y];
                cnt++;
 
                if (min > map[next_x][next_y])
                    min = map[next_x][next_y];
            }
        }
 
        if (cnt == 4)
            sum -= min;
 
        if (sum > max)
            max = sum;
 
    }
}
cs
저작자표시 비영리 변경금지

'공부 > 알고리즘문제' 카테고리의 다른 글

백준 1182 [비트 마스크] 부분집합의 합  (0) 2018.07.29
백준 14503 로봇 청소기  (0) 2017.05.01
백준 7562 나이트의 이동  (0) 2017.04.15
백준 2178 미로 탐색  (0) 2017.04.15
백준 2644 촌수계산  (0) 2017.04.15

티스토리툴바