8972번: 미친 아두이노

요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다.

www.acmicpc.net

 

풀이 방법

입력으로 주어진 방향대로 종수가 움직였을 때, 보드의 상태를 구하는 프로그램을 구하는 문제였습니다.

 

  1. 먼저, 종수가 아두이노를 8가지 방향(수직, 수평, 대각선)으로 이동시키거나, 그 위치에 그대로 놔둔다.
  2. 종수의 아두이노 위치 =  미친 아두이노 위치 게임 오버
  3. 종수의 위치를 (r1,s1), 미친 아두이노의 위치를 (r2, s2)라고 했을 때, |r1-r2| + |s1-s2|가 가장 작아지는 방향으로 이동
  4. 종수의 아두이노 위치 =  미친 아두이노 위치 게임 오버
  5. 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
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_BJ_8972_미친아두이노 {
    
    static class info{
        int x, y;
 
        public info(int x, int y) {
            super();
            this.x = x;
            this.y = y;
        }
        
    }
    
    static int R,C;
    static char [][] map;
    
    static Queue<info> jongsoo = new LinkedList<>();
    static Queue<info> crazy = new LinkedList<>();
    
    static int [] dx = {0,1,1,1,0,0,0,-1,-1,-1};
    static int [] dy = {0,-1,0,1,-1,0,1,-1,0,1};
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        
        map = new char[R][C];
        
        for(int i=0;i<R;i++) {
            String command = br.readLine();
            for(int j=0;j<C;j++) {
                map[i][j] = command.charAt(j);
                if(map[i][j]=='I') jongsoo.add(new info(i,j));
                else if(map[i][j]=='R') crazy.add(new info(i,j));
            }
        }
        
        int count=1;
        
        boolean flag = true;
        String direction = br.readLine();
        for(int i=0;i<direction.length();i++) {
            if(!jongsoo_move(direction.charAt(i)-48)) {
                flag = false;
                break;
            }
            if(!crazy_move()) {
                flag = false;
                break;
            }
            map();
            count++;
        }
        if(!flag) System.out.println("kraj "+ count);
        else print();
    }
    
    
    public static boolean jongsoo_move(int dir) {
        info temp = jongsoo.poll();
        
        int nx = temp.x + dx[dir];
        int ny = temp.y + dy[dir];
 
        if(map[nx][ny]=='R') return false;
        else {
            jongsoo.add(new info(nx,ny));
            if(dir!=5) {
                map[nx][ny] = map[temp.x][temp.y];
                map[temp.x][temp.y] = '.';
            }
            return true;
        }
    }
    
    public static boolean crazy_move() {
        int[][] temp = new int[R][C];
        
        info js = jongsoo.peek();
        
        int jsX = js.x;
        int jsY = js.y;
        
        while(!crazy.isEmpty()) {
            
            info cr = crazy.poll(); 
            
            int len = Integer.MAX_VALUE;
            int dir = 0;
            for(int j=1;j<10;j++) {
                if(j==5) continue;
                int nx = cr.x+dx[j];
                int ny = cr.y+dy[j];
                
                if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
                
                int distance = Math.abs(jsX-nx) + Math.abs(jsY-ny);
                
                if(distance<len) {
                    len = distance;
                    dir = j;
                }
            }
            
            int moveX = cr.x+dx[dir];
            int moveY = cr.y+dy[dir];
            
            
            if(map[moveX][moveY]=='I') {
                return false;
            }
            
            temp[moveX][moveY] += 1;
        }
        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                if(temp[i][j] == 1) {
                    crazy.add(new info(i, j));
                }
            }
        }
        
        return true;
    }
    
    public static void map() {
        for(int i=0;i<R;i++) Arrays.fill(map[i], '.');
        
        info js = jongsoo.peek();
        
        map[js.x][js.y] = 'I';
        
        for(int i=0;i<crazy.size();i++) {
            info cr = crazy.poll();
            map[cr.x][cr.y] = 'R';
            crazy.add(new info(cr.x, cr.y));
        }
    }
    
    public static void print() {
        for(int i=0;i<R;i++) {
            for(int j=0;j<C;j++) {
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }
 
}
 
 cs

 

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

백준 15686 치킨 배달 [JAVA]  (0) 2021.10.23
백준 1406번 에디터 [JAVA]  (0) 2021.10.20
백준 23056번 참가자 명단 [JAVA]  (0) 2021.10.17
백준 8911번 거북이 [JAVA]  (0) 2021.10.13
백준 6137번 문자열 생성 [JAVA]  (0) 2021.09.26

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

 

23056번: 참가자 명단

첫째 줄에 학급 수인 $N$과 학급당 신청 가능한 인원수 $M$이 주어진다. ($N$은 짝수이고 $2\leq N \leq 10$, $1\leq M \leq 10$) 둘째 줄부터 신청된 순서대로 학생의 학급과 이름이 주어진다. 학생의 학급은

www.acmicpc.net

 

풀이 방법

N개의 학급에 최대 M명까지 선착순으로 참가할 수 있는 참가자 명단을 출력하는 문제였습니다.

 

  • 청팀 -> 백팀 순으로 출력
  • 학급 오름차순
  • 이름의 길이가 짧은 것부터, 사전 순으로

위에 3가지 조건을 만족시켜 참가자 명단을 출력해주면 됩니다.

 

저는 청팀과 백팀을 따로 저장하기 위해 odd, even 리스트를 이용하여 최대 M명까지 넣고 정렬을 한 뒤, 각각 출력해주었습니다.

 

코드

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main_BJ_23056_참가자명단 {
    
    public static class info implements Comparable<info>{
        int num;
        String name;
        
        public info(int num, String name) {
            super();
            this.num = num;
            this.name = name;
        }
 
        @Override
        public int compareTo(info o) {
            if(this.num==o.num) {
                if(this.name.length()==o.name.length()) return this.name.compareTo(o.name);
                return this.name.length() - o.name.length();
            }
            return this.num-o.num;
        }
 
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        
        ArrayList<info> odd = new ArrayList<>(); //홀
        ArrayList<info> even = new ArrayList<>(); //짝
        
        
        st = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        int [] school = new int[N+1];
        
        
        while(true) {
            st = new StringTokenizer(br.readLine());
            
            int num = Integer.parseInt(st.nextToken());
            String name = st.nextToken();
            
            if(num==0 && name.equals("0")) break;
            
            if(num%2==0 && school[num]<M) {
                even.add(new info(num, name));
                school[num]++;
            }
            else if(num%2==1 && school[num]<M) {
                odd.add(new info(num,name));
                school[num]++;
            }
        }
        
        Collections.sort(odd);
        Collections.sort(even);
        
        for(int i=0;i<odd.size();i++) {
            sb.append(odd.get(i).num+" "+odd.get(i).name+"\n");
        }
        
        for(int i=0;i<even.size();i++) {
            sb.append(even.get(i).num+" "+even.get(i).name+"\n");
        }
        
        System.out.println(sb.toString());
 
    }
 
}
 cs

 

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

백준 1406번 에디터 [JAVA]  (0) 2021.10.20
백준 8972번 미친 아두이노 [JAVA]  (0) 2021.10.19
백준 8911번 거북이 [JAVA]  (0) 2021.10.13
백준 6137번 문자열 생성 [JAVA]  (0) 2021.09.26
백준 16562 친구비 [JAVA]  (0) 2021.09.21
 

8911번: 거북이

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 컨트롤 프로그램이 주어진다. 프로그램은 항상 문제의 설명에 나와있는 네가지 명령으로만 이루어져

www.acmicpc.net

 

풀이 방법

거북이 로봇에게 내릴 수 있는 명령은 4가지

  1. F: 한 눈금 앞으로
  2. B: 한 눈금 뒤로
  3. L: 왼쪽으로 90도 회전
  4. R: 오른쪽으로 90도 회전 

거북이가 지나간 영역을 모두 포함하는 가장 작은 직사각형 넓이를 구하는 문제였습니다.

 

거북이 좌표를 nowX, nowY 변수에 담아두고 움직이면서 최소 X,Y 값 최대 X,Y값을 구해 이동이 다 끝난 뒤 넓이를 계산해주었습니다.

 

코드

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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main_BJ_8911_거북이 {
    
    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));
        StringBuilder sb = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine());
        
        for(int i=0;i<T;i++) {
            int minX=0, minY=0, maxX=0, maxY=0, dir=0, nowX=0, nowY=0; //초기값 북쪽
            
            String command = br.readLine();
            
            for(int j=0;j<command.length();j++) {
                char c = command.charAt(j);
                
                if(c=='F') { //한 눈금 앞으로
                    nowX = nowX+dx[dir];
                    nowY = nowY+dy[dir];
                }else if(c=='B') { //한 눈금 뒤로
                    nowX = nowX-dx[dir];
                    nowY = nowY-dy[dir];
                }else if(c=='L') { // 왼쪽으로 90도
                    if(dir==0) dir=3;
                    else dir--;
                }else if(c=='R') { // 오른쪽으로 90도
                    if(dir==3) dir=0;
                    else dir++;
                }
                
                minX = Math.min(minX, nowX);
                minY = Math.min(minY, nowY);
                maxX = Math.max(maxX, nowX);
                maxY = Math.max(maxY, nowY);
            }
            sb.append((Math.abs(minX)+Math.abs(maxX))*(Math.abs(minY)+Math.abs(maxY))+"\n");
        }
        System.out.println(sb.toString());
    }
 
}
 cs

 

 

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

백준 8972번 미친 아두이노 [JAVA]  (0) 2021.10.19
백준 23056번 참가자 명단 [JAVA]  (0) 2021.10.17
백준 6137번 문자열 생성 [JAVA]  (0) 2021.09.26
백준 16562 친구비 [JAVA]  (0) 2021.09.21
백준 2531번 회전 초밥 [JAVA]  (0) 2021.09.17
 

6137번: 문자열 생성

첫 번째 줄에 문자열 S의 길이 N이 주어진다. (N <= 2,000) 이후 N개의 줄에 S를 이루는 문자들이 주어진다.

www.acmicpc.net

 

풀이 방법

  • 문자열 S의 가장 앞의 문자 하나를 문자열 T의 마지막에 추가
  • 문자열 S의 가장 뒤의 문자 하나를 문자열 T의 마지막에 추가

문자열 T들 중 사전으로 가장 빠른 문자열을 출력하는 문제였습니다.

 

 

코드

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
 
public class Main_BJ_6137_문자열생성 {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Character> result = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        
        int N = Integer.parseInt(br.readLine());
        
        char [] alpabet = new char[N];
        
        for(int i=0;i<N;i++) {
            String word = br.readLine();
            alpabet[i] = word.charAt(0);
        }
        
        int start=0, end=N-1;
        while(start<=end) {
            if((int)alpabet[start]<(int)alpabet[end]) {
                result.add(alpabet[start++]);
            }else if((int)alpabet[start]==(int)alpabet[end]) {
                int front = start, back=end;
                boolean check = true;
                
                while(alpabet[front]==alpabet[back]) {
                    if(back>0) back--;
                    if(front<N-1) front++;
                    
                    if((int)alpabet[front]<(int)alpabet[back]) check=true;
                    else if((int)alpabet[front]>(int)alpabet[back]) check=false;
                }
                
                if(check) result.add(alpabet[start++]);
                else result.add(alpabet[end--]);
                
                
            }else  {
                result.add(alpabet[end--]);
            }
        }
        
        for(int i=0;i<result.size();i++) {
            if(i!=0 && i%80==0) sb.append("\n");
            sb.append(result.get(i));
        }
        System.out.println(sb.toString());
    }
}
 cs

 

 

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

백준 23056번 참가자 명단 [JAVA]  (0) 2021.10.17
백준 8911번 거북이 [JAVA]  (0) 2021.10.13
백준 16562 친구비 [JAVA]  (0) 2021.09.21
백준 2531번 회전 초밥 [JAVA]  (0) 2021.09.17
백준 1520 내리막길 [JAVA]  (0) 2021.09.10
 

16562번: 친구비

첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (

www.acmicpc.net

 

 

풀이 방법

이 문제는 가장 적은 비용으로 모든 사람과 친구가 되는 방법을 구하는 문제였습니다.

 

1) 친구가 아닌 경우 친구 사귀기

    이때! 친구비가 더 적은걸로 친구비 변경해주기

2) M번의 친구 사귀기가 끝나면 한명씩 확인하면서 친구비 계산

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_BJ_16562_친구비 {
    
    static int N,M,K;
    static int [] parents, friendFee;
    static boolean [] check;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken()); //학생수
        M = Integer.parseInt(st.nextToken()); //친구관계수 
        K = Integer.parseInt(st.nextToken()); //가지고 있는 돈
        
        friendFee = new int[N+1];
        parents = new int[N+1];
        check = new boolean[N+1];
        
        for(int i=1;i<parents.length;i++) parents[i] = i;
        
        st = new StringTokenizer(br.readLine());
        for(int i=1;i<friendFee.length;i++) friendFee[i] = Integer.parseInt(st.nextToken());
        
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            union(a,b);
        }
        
        int friend=0, answer=0;
        for(int i=1;i<parents.length;i++) {
            int temp = find(i);
            if(check[temp]) {
                friend++;
                continue;
            }
            if(K-friendFee[i]>=0) {
                friend++;
                answer+=friendFee[i];
                K-=friendFee[i];
                check[temp] = true;
            }
            
        }
        System.out.println(friend==N?answer:"Oh no");
 
    }
    
    public static void union(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);
        
        if(aRoot<bRoot) parents[bRoot] = aRoot;
        else parents[aRoot]= bRoot;
        
        if(friendFee[aRoot]<friendFee[bRoot]) friendFee[bRoot] = friendFee[aRoot];
        else friendFee[aRoot] = friendFee[bRoot];
    }
    
    public static int find(int x) {
        if(parents[x]==x) return x;
        return parents[x]=find(parents[x]);
    }
 
}
 cs

 

 

 

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

백준 8911번 거북이 [JAVA]  (0) 2021.10.13
백준 6137번 문자열 생성 [JAVA]  (0) 2021.09.26
백준 2531번 회전 초밥 [JAVA]  (0) 2021.09.17
백준 1520 내리막길 [JAVA]  (0) 2021.09.10
백준 17121 연구소2 [JAVA]  (0) 2021.09.02
 

2531번: 회전 초밥

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤

www.acmicpc.net

 

풀이 방법

손님이 먹을 수 있는 초밥 가짓수의 최댓값을 구하는 문제였습니다.

 

몇 번의 초밥을 먹었는지 확인할 수 있는 배열 : check []

종류별로 몇 개 먹었는지 확인할 변수 : count

 

1) 처음 연속해서 k개를 먹었을 경우 몇 번의 초밥과 종류별로 몇 개 먹었는지 확인

2) start=1, end=k로 한 칸씩 ++하면서 종류별로 먹은 최대 초밥 수 max 변수에 담기

3) start = N 인 경우 즉, 끝까지 확인한 경우 종료

 

 

코드

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_BJ_2531_회전초밥 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int max=0;
        
        st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken()); //접시수
        int d = Integer.parseInt(st.nextToken()); //초밥 수
        int k = Integer.parseInt(st.nextToken()); //연속해서 먹는 접시수
        int c = Integer.parseInt(st.nextToken()); //쿠폰번호
        
        int [] sushi = new int[N];
        for(int i=0;i<N;i++) {
            sushi[i] = Integer.parseInt(br.readLine());
        }
        
        int [] check = new int[d+1];
        int count=0;
        
        for(int i=0;i<k;i++) {
            if(check[sushi[i]]==0) count++;
            check[sushi[i]]++;
        }
        
        max = count;
        int start=1, end=k;
        while(true) {
            
            if(check[sushi[start-1]]==1) count--;
            check[sushi[start-1]]--;
            
            if(check[sushi[end]]==0) count++;
            check[sushi[end]]++;
            
            if(check[c]==0) max = Math.max(max, count+1);
            else max = Math.max(max, count);
            
            start++; end++;
            if(end==N) end=0;
            if(start==N) break;
        }
        System.out.println(max);
            
    }
}
 cs

 

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

백준 6137번 문자열 생성 [JAVA]  (0) 2021.09.26
백준 16562 친구비 [JAVA]  (0) 2021.09.21
백준 1520 내리막길 [JAVA]  (0) 2021.09.10
백준 17121 연구소2 [JAVA]  (0) 2021.09.02
백준 16236번 아기 상어 [JAVA]  (0) 2021.08.29

 

 

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
 

1520번: 내리막 길

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으

www.acmicpc.net

 

풀이 방법

이 문제는 (0,0)에서 출발해 오른쪽 아래인(N-1,M-1)위치까지 내리막길로만 이동해서 도착할 수 있는 경로의 수를 구하는 문제였습니다.

1) DFS로 풀기 -> 시간초과 발생

2) DFS + DP로 풀기

 

처음에는 단순히 DFS로 이 문제를 풀었는데

DFS로 풀 경우, 이미 갔었던 경로를 다시 확인하기 때문에 시간초과가 발생했습니다.

 

그래서 두번째로 푼 방법이 DFS + DP를 이용해 풀었습니다.

(N-1,M-1)위치까지 이동했을 경우에는 DP에 경로의 개수를 저장해 두고, 다른 점에서 또 탐색을 할 경우에 해당 경로를 더해주는 방식으로 구현했습니다.

 

코드

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;
import java.util.StringTokenizer;
 
public class Main_BJ_1520_내리막길 {
    
    static int N,M;
    static int [][] map, route;
    
    static int [] dx= {-1,0,1,0};
    static int [] dy= {0,1,0,-1};
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        map = new int[N][M];
        route = new int[N][M];
        
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                route[i][j] = -1;
            }
        }
        System.out.println(dfs(0,0));
        
        for(int i=0;i<N;i++) {
            for(int j=0;j<M;j++) {
                System.out.print(route[i][j]+" ");
            }
            System.out.println();
        }
    }
    
    public static int dfs(int x, int y) {
        if(x==N-1 && y==M-1) {
            return 1 ;
        }
        
        if(route[x][y]!=-1) return route[x][y];
        
        route[x][y]=0;
        for(int i=0;i<4;i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(range(nx,ny)&&map[nx][ny]<map[x][y]) {
                route[x][y]+=dfs(nx,ny);
            }
        }
        return route[x][y];
    }
    
    public static boolean range(int x, int y) {
        return x>=0 && x<N && y>=0 && y<M;
    }
 
}
 cs

 

 

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

백준 16562 친구비 [JAVA]  (0) 2021.09.21
백준 2531번 회전 초밥 [JAVA]  (0) 2021.09.17
백준 17121 연구소2 [JAVA]  (0) 2021.09.02
백준 16236번 아기 상어 [JAVA]  (0) 2021.08.29
백준 9081번 단어 맞추기 [JAVA]  (0) 2021.07.08
 

17141번: 연구소 2

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이

www.acmicpc.net

 

풀이 방법

모든 빈칸에 바이러스를 퍼뜨리는 최소 시간을 구하는 문제였습니다.

 

저는 먼저 이렇게 크게 

1. 바이러스가 놓일 수 있는 연구소 위치를 list에 담기

2. 조합을 이용해 전체 바이러스 개수 중 M개 선택하기

3. 선택한 바이러스 퍼뜨리기

4. 바이러스가 퍼지는 최소 시간 구하기

이 순서로 구현했습니다.

 

조합을 이용해 M개의 바이러스 놓을 칸을 정했다면 spread() 메서드에서 상 하 좌 우로 이동하면서

바이러스를 퍼지게했습니다. 모든 바이러스가 퍼진 뒤에는, 최소 시간을 구해야 하기 때문에 time() 메서드를 통해서

모든 빈 칸에 바이러스가 퍼졌는지 확인과 함께 퍼뜨리는 최소 시간을 구해주었습니다.

이렇게 모든 바이러스가 놓일 수 있는 경우를 확인한 후 가장 최소 시간을 마지막에 출력해주었습니다.

 

 

코드

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
131
132
133
134
135
136
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_BJ_17121_연구소2 {
    
    static class info{
        int x, y;
 
        public info(int x, int y) {
            super();
            this.x = x;
            this.y = y;
        }
        
    }
    
    static int N,M, time = Integer.MAX_VALUE;
    static int [][] map, copy;
    
    static int [] dx = {-1,0,1,0};
    static int [] dy = {0,1,0,-1};
 
    static ArrayList<info> list = new ArrayList<>();
    static ArrayList<info> select = new ArrayList<>();
    static Queue<info> queue = new LinkedList<>();
    static boolean [][] selected;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); //연구소 크기
        M = Integer.parseInt(st.nextToken()); //바이러스 개수
        
        map = new int[N][N];
        selected = new boolean[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]==1) map[i][j]= -1;
                else if(map[i][j]==2) {
                    list.add(new info(i,j));
                    map[i][j] =0;
                }
            }
        }
        comb(0,0);
        if(time==Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(time);
    }
    
    public static void comb(int cnt, int start) {
        if(cnt==M) {
            // 바이러스 퍼지기 & 최소 시간 확인
            spread();
            return;
        }
        
        for(int i=start;i<list.size();i++) {
            int x = list.get(i).x;
            int y = list.get(i).y;
            if(selected[x][y]) continue;
            
            select.add(new info(x,y));
            selected[x][y] = true;
            
            comb(cnt+1,i+1);
            selected[x][y] = false;
            select.remove(select.size()-1);
        }
        
    }
    
    public static void spread() {
        
        transfer();
        copy();
    
        while(!queue.isEmpty()) {
            info temp = queue.poll();
            
            for(int i=0;i<4;i++) {
                int nx = temp.x+dx[i];
                int ny = temp.y+dy[i];
                
                if(range(nx,ny) && copy[nx][ny]==0 && !selected[nx][ny]) {
                    copy[nx][ny] = copy[temp.x][temp.y]+1;
                    queue.add(new info(nx,ny));
                }
            }
        }
        if(time()!=-1 && time>time()) time=time();
    }
    
    public static void copy() {
        copy = new int[N][N];
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                copy[i][j]=map[i][j];
            }
        }
    }
    
    public static boolean range(int x, int y) {
        return x>=0 && x<N && y>=0 && y<N;
    }
    
    public static void transfer() {
        for(int i=0;i<select.size();i++) {
            queue.add(new info(select.get(i).x, select.get(i).y));
        }
    }
    
    public static int time() {
        int min=0, count=0;
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                if(copy[i][j]>min) min = copy[i][j];
                if(copy[i][j]==0) count++;
            }
        }
        if(count!=M) return -1;
        
        return min;    
    }
 
}
 
 cs

 

 

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

백준 2531번 회전 초밥 [JAVA]  (0) 2021.09.17
백준 1520 내리막길 [JAVA]  (0) 2021.09.10
백준 16236번 아기 상어 [JAVA]  (0) 2021.08.29
백준 9081번 단어 맞추기 [JAVA]  (0) 2021.07.08
백준 1713번 후보 추천하기 [JAVA]  (1) 2021.07.04

+ Recent posts

티스토리툴바