SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

풀이 방법

이 문제는 도착점에 대응하는 출발점을 찾는 문제였습니다.

 

여러 출발점에서 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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution_1210_Ladder1 {
    
    static int [][] map;
    static int N=100, arriveX, arriveY, answer;
    
    static int [] dx = {0,0,-1};
    static int [] dy = {-1,1,0};
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        
        for(int tc=0;tc<10;tc++) {
            int t = Integer.parseInt(br.readLine());
            
            map = new int[N][N];
            for(int i=0;i<N;i++) {
                st = new StringTokenizer(br.readLine());
                for(int j=0;j<N;j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                    if(map[i][j]==2) {
                        arriveX = i;
                        arriveY = j;
                    }
                }
            }
            move(arriveX, arriveY);
            sb.append("#"+t+" "+answer+"\n");
        }
        System.out.println(sb.toString());
 
    }
    
    public static void move(int x, int y) {
        
        while(true) {
            if(x==0) {
                answer = y;
                break;
            }
            for(int i=0;i<3;i++) {
                int nx = x+dx[i];
                int ny = y+dy[i];
                
                if(range(nx,ny) && map[nx][ny]==1) {
                    map[x][y] = 3;
                    x = nx; y=ny;
                }
            }
        }
    }
    
    public static boolean range(int x, int y) {
        return x>=0 && x<N && y>=0 && y<N;
    }
 
}
 cs

 

'문제 > SWEA' 카테고리의 다른 글

[SWEA 5658] 보물상자 비밀번호 (JAVA)  (0) 2021.09.10
[SWEA 1227] 미로2 (JAVA)  (0) 2021.03.16
[SWEA 4012] 요리사 (JAVA)  (1) 2021.03.16
 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

풀이 방법

보물 상자에 적힌 숫자로 만들 수 있는 모든 수 중 K번째로 큰 수를 10진수로 만들어 출력하는 문제였습니다.

 

1. 각 변에는 동일한 개수의 숫자가 있다.

2. 시계 방향으로 회전한다.

3. 크기 순서를 셀 때 중복된 수는 세지 않는다.

이를 바탕으로

 

동일한 길이의 비밀번호를 만들기 위해

1. 숫자의 길이인 N을 4로 나누어 각 변에 숫자가 몇 개씩 들어가야 하는지 확인

2. list에 각 숫자 담기

3. N/4개씩 끊어 result에 담기

4. 시계 방향으로 회전하기 때문에 list맨뒤에 있는 값 맨 앞으로 넣어주기

위의 2 ~ 4번 N/4번 반복해준 뒤,

 

result에 담긴 값 내림차순으로 정렬해 K번째의 수를 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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
 
public class Solution_5658_보물상자비밀번호 {
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringBuilder answer = new StringBuilder();
        
        StringTokenizer st;
        
        List<Character> list = new ArrayList<>();
        List<String> result = new ArrayList<>();
        
        int T = Integer.parseInt(br.readLine());
        
        for(int tc=1;tc<=T;tc++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken())/4; //숫자개수
            int K = Integer.parseInt(st.nextToken()); //k번째수
            
            String num = br.readLine();
            for(int i=0;i<num.length();i++) list.add(num.charAt(i));
            
            for(int i=0;i<N;i++) {
                int count=0;
                for(int j=0;j<num.length();j++) {
                    sb.append(list.get(j));
                    count++;
                    if(count==N) {
                        if(!result.contains(sb.toString())) {
                            result.add(sb.toString());
                        }
                        sb.setLength(0);
                        count=0;
                    }
                }
                char c = list.remove(list.size()-1);
                list.add(0,c);
            }
            
            Collections.sort(result, Collections.reverseOrder());
            
            for(int i=0;i<result.size();i++) {
                if(i==K-1) {
                    answer.append("#"+tc+" "+Integer.parseInt(result.get(i),16)+"\n");
                    break;
                }
            }
            list.clear();
            result.clear();
            
        }
        System.out.println(answer.toString());
 
    }
 
}
 cs

 

 

'문제 > SWEA' 카테고리의 다른 글

[SWEA 1210] Ladder1 (JAVA)  (0) 2021.09.16
[SWEA 1227] 미로2 (JAVA)  (0) 2021.03.16
[SWEA 4012] 요리사 (JAVA)  (1) 2021.03.16

문제

- 100*100 행렬의 형태로 만들어진 미로에서 출발점으로부터 도착지점까지 갈 수 있는 길이 있는지 판단하는 문제

- 1은 벽, 0은 길 2는 출발점, 3은 도착점

 

풀이방법

- DFS알고리즘을 이용

- 상, 하, 좌, 우로 이동하여 출발지점에서 도착지점까지 갈 수 있는지 판단

- 만약 도착지점에 도달했을 경우 리턴

 

 

코드

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.IOException;
import java.io.InputStreamReader;
 
public class Solution_D4_1227_미로2 {
    static StringBuilder sb = new StringBuilder();
    static int [][] map;
    static boolean[][] visited;
    static int startX, startY,find;
    static int [] dx = {-1,0,1,0};
    static int [] dy = {0,1,0,-1};
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        for(int tc=1;tc<=10;tc++) {
            
            int N = Integer.parseInt(br.readLine());
            
            map = new int[100][100];
            visited = new boolean[100][100];
            
            for(int i=0;i<100;i++) {
                String str = br.readLine();
                for(int j=0;j<100;j++) {
                    map[i][j]=str.charAt(j)-48;
                    if(map[i][j]==2) {
                        startX = i; startY = j;
                    }
                }
            }
            find=0;
            sb.append("#"+N+" ");
            dfs(startX, startY);
            sb.append(find+"\n");
            
        }
        System.out.println(sb.toString());
 
    }
    
    public static void dfs(int x, int y) {
        if(find==1) return;
        visited[x][y] = true;
        
        for(int i=0;i<4;i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(map[nx][ny]==3) {
                find=1;
                return;
            }
            
            if(check(nx,ny) && !visited[nx][ny] && (map[nx][ny]==0)) {
                dfs(nx,ny);
            }
        }    
    }
    
    public static boolean check(int x, int y) {
        return x>=0 && y>=0 && x<100 && y<100;
    }
 
}
 cs

 

'문제 > SWEA' 카테고리의 다른 글

[SWEA 1210] Ladder1 (JAVA)  (0) 2021.09.16
[SWEA 5658] 보물상자 비밀번호 (JAVA)  (0) 2021.09.10
[SWEA 4012] 요리사 (JAVA)  (1) 2021.03.16

문제

- 식재료 N/2개씩 나누어 두 개의 요리를 만들어 두 음식 맛의 차이가 최소가 되도록 재료를 배분해야하는 문제

 

 

풀이방법

- 조합을 이용해 N/2 식재료를 선택후, 선택한 식재료를 이용해 A음식을, 비선택한 식재료를 이용해 B음식을 통해 맛 차이 비교를 해주었습니다.

 

 

코드

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution_4012_요리사 {
    static int [][]food;
    static boolean []visited;
    static int N, min;
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;
        StringBuilder sb = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine());
        
        for(int tc=1;tc<=T;tc++) {
            min=Integer.MAX_VALUE;
            
            N= Integer.parseInt(br.readLine());
            
            food = new int[N][N];
            visited = new boolean[N];
            
            for(int i=0;i<N;i++) {
                st = new StringTokenizer(br.readLine()," ");
                for(int j=0;j<N;j++) {
                    food[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            sb.append("#"+tc+" ");
            comb(0,0);
            sb.append(min+"\n");
        }
        System.out.println(sb.toString());
    }
    
    public static void comb(int cnt, int start) {
        if(cnt==N/2) {
            check();
            return;
        }
        
        for(int i=start; i<N;i++) {
            visited[i] = true;
            comb(cnt+1,i+1);
            visited[i] = false;
        }
    }
    
    public static void check() {
        int A=0, B=0, result=0;
        
        for(int i=0;i<N-1;i++) {
            for(int j=i+1;j<N;j++) {
                if(visited[i] && visited[j]) {
                    A+=food[i][j]+food[j][i];
                }
                else if(!visited[i] && !visited[j]) {
                    B+=food[i][j]+food[j][i];
                }
            }
        }
        result = Math.abs(A-B);
        min = Math.min(result, min);
    }
}
 cs

 

 

 

'문제 > SWEA' 카테고리의 다른 글

[SWEA 1210] Ladder1 (JAVA)  (0) 2021.09.16
[SWEA 5658] 보물상자 비밀번호 (JAVA)  (0) 2021.09.10
[SWEA 1227] 미로2 (JAVA)  (0) 2021.03.16

+ Recent posts

티스토리툴바