반응형

백준 11559 Puyo Puyo

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

 

11559번: Puyo Puyo

총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.

www.acmicpc.net

Comment
기본적인 탐색 + 구현 시뮬레이션 문제
확실히 구현이 들어가니까 실수하는게 생기고 실수했을 때 원인찾기가 어렵다. 지금은 디버깅으로 가능하지만 코테에서는 신경을 많이 써서 해야할 듯?

Hint

  • 기본적인 BFS이동을 담을 movePoint
  • 방문체크 visited
  • 게임판 puyoMap
  • 연쇄횟수
  • 매 라운드가 있어야하기에 puyoClear(boolean)
  • 연쇄가 발생했을 때 뿌요를 지울 ArrayList

아직 깔끔하게 구현은 못하겠지만 어느걸 써야할지는 계속 생각하며 풀어야 함

Solution
1. 탐색하고 탐색된 좌표 저장
2. 탐색된 좌표가 4개 이상일 때 puyoClear = true, 실제로 지울 clearPuyoMap List에 추가
3. clearPuyoMap 기반으로 뿌요들을 아래로 내려줌
4. 한번 지워진 상태(puyoClear == true)라면 1~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
106
107
package Baekjoon.gold;
 
import java.io.*;
import java.util.*;
 
public class p11559 {
    static final int[][] movePoint = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static boolean[][] visited = new boolean[12][6];
    static char[][] puyoMap = new char[12][6];
    static int count = 0;
    static int n = 12;
    static boolean puyoClear = false;
    static ArrayList<int[]> accumulatePuyoMap = new ArrayList<>();
    static ArrayList<int[]> clearPuyoMap = new ArrayList<>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < n; i++) {
            puyoMap[i] = br.readLine().toCharArray();
        }
 
        do {
            puyoClear = false;
            puyoGame();
            if (puyoClear) {
                count++;
                puyoMove();
            }
            clearPuyoMap.clear();
            visited = new boolean[12][6];
        } while (puyoClear);
        System.out.println(count);
 
    }
 
    static void puyoGame() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 6; j++) {
                if (puyoMap[i][j] != '.' && !visited[i][j]) {
                    bfs(i, j, puyoMap[i][j]);
                }
            }
        }
    }
 
    static void bfs(int x, int y, char puyoColor) {
        Queue<int[]> q = new LinkedList<>();
        visited[x][y] = true;
        q.add(new int[]{x, y});
        accumulatePuyoMap.clear();
        accumulatePuyoMap.add(new int[]{x, y});
 
        while (!q.isEmpty()) {
            int[] nowXY = q.poll();
            for (int[] moveXY : movePoint) {
                int nowX = nowXY[0] + moveXY[0];
                int nowY = nowXY[1] + moveXY[1];
                if (nowX >= 0 && nowY >= 0 &&
                        nowX < 12 && nowY < 6 &&
                        puyoColor == puyoMap[nowX][nowY] &&
                        !visited[nowX][nowY]) {
                    visited[nowX][nowY] = true;
                    q.add(new int[]{nowX, nowY});
                    accumulatePuyoMap.add(new int[]{nowX, nowY});
                }
            }
        }
        if (accumulatePuyoMap.size() >= 4) {
            puyoClear = true;
            clearPuyoMap.addAll(accumulatePuyoMap);
        }
    }
 
    static void puyoMove() {
        //4개 이상인 뿌요를 .으로 초기화
        for (int[] clearXY : clearPuyoMap) {
            puyoMap[clearXY[0]][clearXY[1]] = '.';
        }
 
        //.을 탐색하며 뿌요를 위로 올려줌
        int[] firstDotPlace = new int[2];
        for (int i = 0; i < 6; i++) {
            boolean firstDotCheck = false;
            Queue<Character> upMovePuyo = new LinkedList<>();
            for (int j = 11; j >= 0; j--) {
                if (puyoMap[j][i] == '.') {
                    if (firstDotCheck) {
                        continue;
                    }
                    firstDotPlace[0] = j;
                    firstDotPlace[1] = i;
                    firstDotCheck = true;
                } else if (firstDotCheck) {
                    upMovePuyo.add(puyoMap[j][i]);
                    puyoMap[j][i] = '.';
                }
            }
            int nowX = firstDotPlace[0];
            int nowY = firstDotPlace[1];
            while (!upMovePuyo.isEmpty()) {
                puyoMap[nowX][nowY] = upMovePuyo.poll();
                nowX--;
            }
        }
    }
}
 
cs

 

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

'공부 > Algorithm' 카테고리의 다른 글

백준 16401 과자 나눠주기 자바로 풀어 본 짧은 글  (0) 2023.12.02
백준 29812번 아니 이게 왜 안돼 자바로 풀어 본 짧은 글  (0) 2023.12.01
백준 2310번 어드벤처 게임 자바로 풀어 본 짧은 글  (0) 2023.11.28
백준 12755번 수면 장애 자바로 풀어 본 짧은 글  (0) 2023.11.21
백준 14494번 다이나믹이 뭐예요? 자바로 풀어 본 짧은 글  (0) 2023.09.15
반응형

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

2310번 어드벤처 게임

 

2310번: 어드벤처 게임

입력은 여러 개의 미로로 주어진다. 각 미로의 첫 줄에는 미로의 방 수를 나타내는 정수 n(1 ≤ n ≤ 1000)이 주어진다. 다음 n 줄에는 각 방의 정보가 주어진다. 각 방의 정보는 방의 내용물을 나타

www.acmicpc.net

Comment
문제 이해하는데 한참 걸렸던 문제 생각보다 구현은 엄청 어렵지는 않았다.
문제 이해를 돕자면 각 줄이 1, 2, 3, 4번 방으로 쭉 나열되는 것이고, E,L,T의 상태를 가진 방 으로 생각하면 편할 것 같다.
다들 쉽게 이해하겠지만 저는 좀 힘들었습니다..

Hint

  • 기본적인 방의 번호와 상태를 담은 mapList
  • 방문을 확인할 배열 visited
  • n번방에 도달했는지 확인하는 success

Solution
문제 이해하기까지도 오래 걸리고, 아직 문해력이 부족한건지 모호했던 부분이 많았던 문제 그래도 직접 해결해서 뿌듯하다

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
package Baekjoon.gold;
 
import java.io.*;
import java.util.*;
 
 
/**
 * 3
 * E 0 2 0
 * L 10 3 0
 * T 15 1 2 0
 *
 * E 빈방, L 레프리콘, T 트롤
 * 두번째 0, 10, 15 금액
 * 레프리콘은 10원 기준
 * 트롤은 15원 기준
 *
 * 1번방 출발 빈방시작
 * 이후의 값은 다 다른 방과 이어지는 번호
 *
 * 처음 모험가가 시작하는 방 번호 1
 *
 * 연결리스트로 추가하기
 *
 */
public class p2310 {
 
    static ArrayList<Room> mapList;
    static boolean[] visited;
    static int n;
    static StringBuilder sb = new StringBuilder();
    static boolean flag;
    static boolean success;
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        n = Integer.parseInt(br.readLine());
        while(n > 0){
            mapList = new ArrayList<>();
            visited = new boolean[n+1];
            int myMoney = 0;
            flag = true;
            success = false;
            //0번방의 필요없는 데이터 주입
            mapList.add(new Room(-1,"NOTHING",-1));
            //
 
            for(int roomNumber = 1; roomNumber <= n; roomNumber++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                Room roomInit = new Room(
                        roomNumber,
                        st.nextToken(),
                        Integer.parseInt(st.nextToken())
                );
 
                int inputNum = Integer.parseInt(st.nextToken());
                while(inputNum > 0){
                    roomInit.roomNumberAdd(inputNum);
                    inputNum = Integer.parseInt(st.nextToken());
                }
                mapList.add(roomInit);
            }
 
            dfs(1, myMoney);
 
            if(!success){
                sb.append("No").append("\n");
            }else{
                sb.append("Yes").append("\n");
            }
            n = Integer.parseInt(br.readLine());
        }
 
        System.out.println(sb);
 
    }
 
    static void dfs(int roomNum, int myMoney){
        if(success){
            return;
        }
        visited[roomNum] = true;
 
        Room nowRoom = mapList.get(roomNum);
        myMoney = nowRoom.visitRoomEvent(myMoney);
        if(myMoney >= 0){
            if(n == roomNum){
                success = true;
                return;
            }
            for(int roomNumber : nowRoom.getLinkedRoomList()){
                if(!visited[roomNumber]) {
                    dfs(roomNumber, myMoney);
                }
            }
        }else{
            visited[roomNum] = false;
            return;
        }
    }
 
    private static class Room{
        int roomNum;
        String roomType;
        int roomMoney;
        final ArrayList<Integer> roomList;
        Room(int roomNumber, String type, int money){
            this.roomMoney = money;
            this.roomNum = roomNumber;
            this.roomList = new ArrayList<>();
            this.roomType = type;
        }
 
        void roomNumberAdd(int number){
            roomList.add(number);
        }
 
        ArrayList<Integer> getLinkedRoomList(){
            return roomList;
        }
 
        int visitRoomEvent(int money){
            if(roomType.equals("L")){
                if(money < this.roomMoney){
                    return this.roomMoney;
                }
            }
            if(roomType.equals("T")){
                if(money < this.roomMoney){
                    return -1;
                }
                money -= roomMoney;
                return money;
            }
            return money;
        }
    }
}
cs

 

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

'공부 > Algorithm' 카테고리의 다른 글

백준 29812번 아니 이게 왜 안돼 자바로 풀어 본 짧은 글  (0) 2023.12.01
백준 11559번 Puyo Puyo 자바로 풀어 본 짧은 글  (0) 2023.11.30
백준 12755번 수면 장애 자바로 풀어 본 짧은 글  (0) 2023.11.21
백준 14494번 다이나믹이 뭐예요? 자바로 풀어 본 짧은 글  (0) 2023.09.15
백준 1680번 쓰레기 수거 자바로 풀어 본 짧은 글  (0) 2023.09.07
반응형

2023번 신기한 소수

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

 

2023번: 신기한 소수

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수

www.acmicpc.net

Comment

 처음에는 소수판별이기 때문에 이전에 배워뒀던 에라토스테네스의 체를 사용하려고 했다. 하지만 이 문제는 메모리제한이 4MB에 N의 범위가 8 즉 최대 10,000,000 천만의 범위이기 때문에 자바의 데이터 최소단위 byte - boolean크기: 1byte로 지정되었을 때 에토체의 boolean배열만 어림잡아 100mb가 넘게된다 때문에 기각.

일반 소수판별 메서드를 생성해서 처리했다.

hint

DFS, 소수판별을 해야한다

Solution

 최종적으로 가지치기 등등 다양하게 하니까 속도가 좀 빨라졌다. 1,3,5,7,9가 아닌 0~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
65
66
67
68
import java.io.*;
import java.util.*;
 
 
public class Main {
    static int[] firstPrime = {2, 3, 5, 7};
    static int n;
    static ArrayList<Integer> magicPrime = new ArrayList<>();//신기한 소수를 담을 리스트
 
//    static int count = 0;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
//        int jari = (int)Math.pow(10, n); // 끝자리까지보기
 
        //4메가면 에토체가 가능한가?
        // 1000000 백만에 1M 4백만이면 끝나는데 안된다.
        //나중에 에토체로 구현되나만 체크해보면 재밌을듯
 
        //한자릿수는 배열을만들자 이걸 가지고 시작
        //이걸로 조합을 다하면 그건 브루트포스아닌가?
        //그래서 DFS느낌으로 가는건가?
 
        //슈도흐름을 생각해보자.
        //1. 한자릿수 prime등록 이후는 전부됨......
        //2. 두번째부터 그 수를 붙여서 prime인지 확인 (n을 입력받은 중단점까지)
        //2_1. DFS를 활용, String에 붙여서 다음 DFS로 이동
        //2_2. 백트래킹도 무조건 넣어야할듯? 한 Depth에서 같은 소수를 여러번 반복해야함
        //3. 중단점을 찾았으면 그 수를 리스트에 추가
        //4. 리스트에 추가된거 출력!
 
        for (int i = 0; i < firstPrime.length; i++) {
            dfs(String.valueOf(firstPrime[i]), 1);
        }
 
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < magicPrime.size(); i++) {
            if(i == magicPrime.size()-1){
                sb.append(magicPrime.get(i));
            }else {
                sb.append(magicPrime.get(i) + "\n");
            }
        }
        System.out.print(sb);
 
    }
 
    static void dfs(String s, int count) {
        if (count == n && isPrime(Integer.valueOf(s))) {//중단점
            magicPrime.add(Integer.valueOf(s));
        }
        if (isPrime(Integer.valueOf(s))) {
            for (int i = 1; i < 10; i += 2) {
                    dfs(s.concat(String.valueOf(i)), count + 1);
            }
        }
    }
 
    static boolean isPrime(int isPrimeNum) {
        for (int i = 2; i <= (int) Math.sqrt(isPrimeNum); i++) {
            if (isPrimeNum % i == 0) {
                return false;
            }
        }
        return true;
    }
}
cs
반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 골드5 달성!  (0) 2023.08.11
백준 2644번 촌수 계산 자바(BFS,DFS)로 풀어 본 짧은 글  (0) 2023.08.03
백준 2583번 영역 구하기 자바로 풀어 본 짧은 글  (0) 2023.07.23
알고리즘 근황  (0) 2023.07.23
백준 11822번 Document 자바로 풀어 본 짧은 글  (0) 2023.06.08
반응형

2583번 영역 구하기

문제 링크 : https://www.acmicpc.net/problem/2583

 

2583번: 영역 구하기

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오

www.acmicpc.net

 

Comment

DFS공부를 시작하면서 만나게 된 문제다. 처음 떠올랐던 아이디어는 이전에 풀었던 색종이 문제처럼 먼저 구현해둔 맵 배열에 칠하고 나머지 갈라진 부분을 DFS로 채워나가자고 생각하고 접근했다.

hint

  • Map을 칠하고 구분된 빈곳을 돌 때마다 count를 해주면 될듯?

Solution

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
import java.io.*;
import java.util.*;
 
public class Main {
 
    static boolean map[][];
    static int count = 0;
 
    static int n, m, k;
 
    static int rectangleSize = 0;
    static ArrayList<Integer> rectangleSizeList = new ArrayList<>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
 
        map = new boolean[m][n];
 
        for(int i = 0; i < k; i++){
            st = new StringTokenizer(br.readLine());
            drawRectangle(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())
                    ,Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
        }
 
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(!map[i][j]){
                    count++;
                    dfs(i, j);
                    rectangleSizeList.add(rectangleSize);
                    rectangleSize = 0;
                }
            }
        }
        Collections.sort(rectangleSizeList);
        StringBuilder sb = new StringBuilder();
        sb.append(count).append("\n");
 
        for(int i = 0; i < rectangleSizeList.size(); i++){
            sb.append(rectangleSizeList.get(i) + " ");
        }
        System.out.println(sb);
    }
 
    static void dfs(int x, int y){
        if(x >= 0 && y >= 0 && x < m && y < n) {
            if (!map[x][y]) {
                map[x][y] = true;
                rectangleSize++;
                dfs(x + 1, y);
                dfs(x - 1, y);
                dfs(x, y + 1);
                dfs(x, y - 1);
            }
        }
    }
    static void drawRectangle(int x1, int y1, int x2, int y2){
        for(int i = y1; i < y2; i++) {
            Arrays.fill(map[i], x1, x2, true);
        }
    }
}
cs

 

Arrays.fill 메서드를 활용해보고 싶어서 사용했고, fill메서드를 안쓰고 각 좌표별로 true체크를 한 후에 칠했으면 조금 더 효율이 좋을 것 같다.

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

'공부 > Algorithm' 카테고리의 다른 글

백준 2644번 촌수 계산 자바(BFS,DFS)로 풀어 본 짧은 글  (0) 2023.08.03
백준 2023번 신기한 소수 자바로 풀어 본 짧은 글  (0) 2023.07.25
알고리즘 근황  (0) 2023.07.23
백준 11822번 Document 자바로 풀어 본 짧은 글  (0) 2023.06.08
백준 21771 가희야 거기서 자는 거 아니야 자바로 풀어 본 짧은 글  (0) 2023.05.31
반응형

 

백준을 건든지는 좀 됐는데 요 최근 실력을 끌어올리고 싶어서

하루 1문제이상 풀이를 목표로 최대한 노력해왔고, 현재 연속 9주 풀이에 도달했다.

수준 낮은 문제더라도 억지로 계속 해왔더니 실력이 좀 늘었다는게 느껴져서 뿌듯하다.

 

일기는 끝이고 앞으로는 약간 재밌는 문제가 있고, 시간 여유가 있으면 다시 포스팅을 신경써서 해보려고 합니다.

공부하는 모두 파이팅!!🔥🔥🔥🔥🔥🔥🔥

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

'공부 > Algorithm' 카테고리의 다른 글

백준 2023번 신기한 소수 자바로 풀어 본 짧은 글  (0) 2023.07.25
백준 2583번 영역 구하기 자바로 풀어 본 짧은 글  (0) 2023.07.23
백준 11822번 Document 자바로 풀어 본 짧은 글  (0) 2023.06.08
백준 21771 가희야 거기서 자는 거 아니야 자바로 풀어 본 짧은 글  (0) 2023.05.31
백준 13717 포켓몬Go 자바로 풀어 본 짧은 글  (0) 2023.05.25
반응형

11822번 Document

바로 한글변환...

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

 

11822번: Document

In the first example, the document must be signed by two officials — the first one accept documents on Mondays, Wednesdays and Fridays, and the second one — on Mondays and Thursdays. The fastest way to sign the document is one of the following: you s

www.acmicpc.net

이 문제를 처음에 이해하기로는 그냥 어느 공무원이든 모두 일처리를 한번씩만 하면 되는 것으로 착각하고 풀었는데, 접근방식이 틀렸었다.

-----

hint

3명의 공무원이 있다면 첫번째 공무원부터 부터 계단식으로 서류통과를 하는 방식이 맞는 방식이다.

입력케이스 하나를 예로 들었을 때

2
0 1 0 0 1
1 1 0 0 0

각각 배열로 선언을 했다 쳤을 때 두번째 줄 a배열, 세번째 줄 b배열로 치면

a[1] 인덱스에서 1을 발견하고 카운트, 이후 b배열로 이동해서 b[2] -> b[3] -> b[4] ->b[0] 으로 이동을 해서 1을 발견한 b[1]

자리에서 멈춘다 그렇다면 이미 한 주의 사이클이 돌았으니 5일 +2일 + 두번째 주의 1일 해서 8이 나오게 된다

-----

solution

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
import java.util.*;
import java.io.*;
 
public class Main {
    static int count = 0;
    static int length = 0;
    //static boolean bool[] = new boolean[5];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int n = Integer.parseInt(br.readLine());
        int[][] al = new int[n][5];
 
 
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 5; j++) {
                al[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        length = n;
        goRepeat(al, 0);
    }
 
    static void goRepeat(int[][] a, int n) {
        if (n == length) {
            if (count % 5 == 0 && count / 5 > 0) {
                System.out.println(count + ((count / 5 - 1) * 2));
                return;
            } else {
                System.out.println(count + (count / 5 * 2));//5일 지날때마다 +2
                return;
            }
        }
        go(a[n], count % 5);
        n++;
        goRepeat(a, n);
 
 
        return;
    }
 
    static void go(int a[], int index) {
        for (int i = 0; i < 5; i++) {
            count++;
 
            if (a[index] == 1) {
                return;
            }
            index = (index + 1) % 5;
        }
 
    }
 
}
cs

실행시간 76ms 

처음엔 배열로 풀려고 하다가 재귀함수를 학습하고싶은 마음에 재귀함수를 통해서 풀어봤다.

진짜 별거아닌 코드같은데 놀랍게도 이틀중 5시간은 써가면서 겨우 구현한 것 같다....

재귀 구현 너무 어렵...

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

'공부 > Algorithm' 카테고리의 다른 글

백준 2583번 영역 구하기 자바로 풀어 본 짧은 글  (0) 2023.07.23
알고리즘 근황  (0) 2023.07.23
백준 21771 가희야 거기서 자는 거 아니야 자바로 풀어 본 짧은 글  (0) 2023.05.31
백준 13717 포켓몬Go 자바로 풀어 본 짧은 글  (0) 2023.05.25
백준 1418 K-세준수 자바로 풀어 본 짧은 글  (0) 2023.05.24
반응형

p21771 가희야 거기서 자는 거 아니야

처음 접근방법은 G의 각 꼭짓점 별로 좌표를 추적해서 좌우에 P가 있는지 탐색해보는 방식으로 접근했었는데, 정확한 이유는 모르겠지만 실패했다.

그래서 생각해 본 방법이 P의 넓이를 구하고 P의 갯수를 카운트했을 때 넓이가 안맞으면  가희가 베개를 사용하고 있는 것으로 판단하기로 해보고 문제를 풀어봤다.

hint

----

P의 갯수를 활용하는 것이 핵심

----

Solution

실행시간 - 124ms

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
import java.util.*;
import java.io.*;
 
class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        int gr = Integer.parseInt(st.nextToken());
        int gc = Integer.parseInt(st.nextToken());
        int pr = Integer.parseInt(st.nextToken());
        int pc = Integer.parseInt(st.nextToken());
        
        char[][] map = new char[r][c];
        
        for(int i = 0; i < r; i++){
            map[i] = br.readLine().toCharArray();
        }
        
        int n = pr * pc; // 60
        int count = 0;
        for(int i = 0; i < r; i++){
            for(int j = 0; j < c; j++){
                if(map[i][j] == 'P'){
                    count++;
                }
            }
        }
        
        if(count == n){
            System.out.println(0);
        }else{
            System.out.println(1);
        }
        
        
        
    }
    
    
}
cs

 

다음에 기회가 된다면 각 꼭짓점 별로 판단하는 방식을 채용해보고 싶다... 정말 최고의 최적화일거같은데 반례가 어느걸까 궁금하다

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

'공부 > Algorithm' 카테고리의 다른 글

알고리즘 근황  (0) 2023.07.23
백준 11822번 Document 자바로 풀어 본 짧은 글  (0) 2023.06.08
백준 13717 포켓몬Go 자바로 풀어 본 짧은 글  (0) 2023.05.25
백준 1418 K-세준수 자바로 풀어 본 짧은 글  (0) 2023.05.24
백준 24444번 너비 우선 탐색 1 자바로 풀어 본 짧은 글  (0) 2023.04.30
반응형

13717번 포켓몬Go

내용은 구현이 익숙한 사람들은 효율을 생각 안하면 쉽게 구현할만한 문제같다.

위의 테스트케이스 기준으로 설명을 하자면.

4마리의 포켓몬을 입력받는데, 각 마리마다 입력받는 값은 Caterpie라는 문자열, 레벨업에 필요한 사탕갯수(12), Caterpie에게 투자할 수 있는 사탕의 갯수이다. 1레벨업을 할 때마다 2개의 사탕을 돌려받는다.

 ----

hint

각자 배열을 선언해서 비교와 연산을 해주면 된다.

----

Solution

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
import java.util.*;
import java.io.*;
 
class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        //pokemon
        //levelupCandy
        //haveCandy
        String[] pokemon = new String[n];
        int[] levelupCandy = new int[n];
        int[] haveCandy = new int[n];
        
        for(int i = 0; i < n; i++){
            pokemon[i] = br.readLine();
            st = new StringTokenizer(br.readLine());
            levelupCandy[i] = Integer.parseInt(st.nextToken());
            haveCandy[i] = Integer.parseInt(st.nextToken());
        }
        //Caterpie
        //12
        //33
        
        int count = 0;
        int tempCount = 0;
        int index = 0;
        int maxCount = 0;
        for(int i = 0; i < n; i++){
            while(haveCandy[i] >= levelupCandy[i]){
                haveCandy[i] -= levelupCandy[i] - 2;
                tempCount++;
            }
            if(maxCount < tempCount){
                maxCount = tempCount;
                index = i;
            }
            count += tempCount;
            tempCount = 0;
        }
        System.out.println(count);
        System.out.println(pokemon[index]);
    }
}
cs

실행시간 - 124ms

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

'공부 > Algorithm' 카테고리의 다른 글

백준 11822번 Document 자바로 풀어 본 짧은 글  (0) 2023.06.08
백준 21771 가희야 거기서 자는 거 아니야 자바로 풀어 본 짧은 글  (0) 2023.05.31
백준 1418 K-세준수 자바로 풀어 본 짧은 글  (0) 2023.05.24
백준 24444번 너비 우선 탐색 1 자바로 풀어 본 짧은 글  (0) 2023.04.30
백준 13023번 ABCDE 자바로 풀어 본 짧은 글  (0) 2023.04.22
반응형

1418번 K-세준수

N까지의 값을 입력받아서 각 수의 소인수분해를 통해 소인수를 받고 해당 소인수의 최댓값을 입력받은 K와 비교해 카운트한 수를 출력

-----

hint

각 소인수를 hashMap에 저장 이후 맥스값 출력

-----

Solution

실행시간 - 3496ms

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
import java.util.*;
import java.io.*;
// 1 2 3 4 5 6 7 8 9 10
// 1 2 3 2 5 3 7 2 3 5
class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine()); 
        int k = Integer.parseInt(br.readLine());
        int[] a = new int[n+1];
        HashMap<Integer, Integer> hs = new HashMap<Integer, Integer>(n+1);
        
        for(int i = 0; i <= n; i++){
            a[i] = i;
            hs.put(i,0);//해시맵 초기화
        }
        
        //1은 되니까 배제
        for(int i = 2; i <= n; i++){//2부터 n까지의 소인수들을 저장
            int soinsu = a[i];
            for(int j = 2; j <= soinsu; j++){
                while(soinsu % j == 0){ 
                    soinsu /= j;
                    hs.put(i, j);
                }
                // 소인수분해 한 값들중에서 max값을 해당 hs에 집어넣는다.
            }
        }
        
        int count = 0;
        for(int i = 1; i < a.length; i++){
            if(hs.get(i) <= k){
                count++;
            }
        }
        System.out.println(count);
    }
}
cs

직접 무식하게 푼거라 효율이 매우 좋지 않음...

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

'공부 > Algorithm' 카테고리의 다른 글

백준 21771 가희야 거기서 자는 거 아니야 자바로 풀어 본 짧은 글  (0) 2023.05.31
백준 13717 포켓몬Go 자바로 풀어 본 짧은 글  (0) 2023.05.25
백준 24444번 너비 우선 탐색 1 자바로 풀어 본 짧은 글  (0) 2023.04.30
백준 13023번 ABCDE 자바로 풀어 본 짧은 글  (0) 2023.04.22
백준 11004번 K번째 수 자바로 풀어 본 짧은 글  (0) 2023.03.25
반응형

24444번 너비 우선 탐색 1

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

 

24444번: 알고리즘 수업 - 너비 우선 탐색 1

첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방

www.acmicpc.net

 

이번엔 BFS... DFS 보다 습득하는데 더 오래 걸린 듯 하다

그나마 이번 문제 풀면서 범위설정이나 조건이나 여러가지로 감을 좀 잡은듯

 

------

hint

해당 번호가 몇번째 순서로 도달했는지 저장하는 배열이 따로 필요

------

Solution

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
 
    static boolean[] isVisit;
    static ArrayList<Integer>[] a;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());
 
        int u, v;
 
        isVisit = new boolean[n+1];
        a = new ArrayList[n+1];
 
        for(int i = 1; i < n + 1; i++){
            a[i] = new ArrayList<Integer>();
        }
 
        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
 
            a[u].add(v);
            a[v].add(u);
        }
 
        for(int i = 1; i < n + 1; i++){
            if(!a[i].isEmpty()) {
                Collections.sort(a[i]);
            }
        }
 
        BFS(r, n, m);
 
    }
 
    static void BFS(int r, int n, int m){ // r이 1이라고 가정했을 때
        Queue<Integer> queue = new LinkedList<>();
 
        int temp;
        int[] count = new int[n+1];
        int countNum = 1;
 
        isVisit[r] = true;
        count[r] = countNum++;
        queue.offer(r);
 
        while(!queue.isEmpty()){
            temp = queue.poll();
            for(int i = 0; i < a[temp].size(); i++) {
                if (!isVisit[a[temp].get(i)]) {//방문하지 않았을 때 실행
                    isVisit[a[temp].get(i)] = true;
                    count[a[temp].get(i)] = countNum++;
                    queue.offer(a[temp].get(i));
                }
            }
        }
 
        for(int i = 1; i < n + 1; i++){
            System.out.println(count[i]);
        }
    }
}
 
cs

 

실행시간 - 1996ms

너무 길어서 최적화좀 해주고싶은데.... BufferedReader말고는 상상이 안됨

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

'공부 > Algorithm' 카테고리의 다른 글

백준 13717 포켓몬Go 자바로 풀어 본 짧은 글  (0) 2023.05.25
백준 1418 K-세준수 자바로 풀어 본 짧은 글  (0) 2023.05.24
백준 13023번 ABCDE 자바로 풀어 본 짧은 글  (0) 2023.04.22
백준 11004번 K번째 수 자바로 풀어 본 짧은 글  (0) 2023.03.25
백준 2164번 카드2 자바로 풀어 본 짧은 글  (0) 2023.03.18

+ Recent posts

티스토리툴바