코테/백준

📖 문제  15990번: 1, 2, 3 더하기 5각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.www.acmicpc.net   💡  풀이 방식• DP 같은 숫자가 2번 이상 연달아 나오면 안 된다는 조건이 있으므로,마지막 숫자를 기준으로 갯수를 센다.  예) 41 = dp[1][1] (1)2 = dp[2][2] (2)3 = dp[3][1] (2,1) + dp[3][2] (1,2) + dp[3][3] (3)4 = dp[4][1] + dp[4][2] + dp[4][3]   = (dp[3][2] + dp[3][3]) + (dp[2][1] + dp[2][3]) + (dp[1][2] + dp..

📖 문제 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 💡 풀이 방식 • 그리디 + 정렬 필요 자료구조 - (보내는 마을, 받는 마을, 박스 개수) 정보를 갖는 객체 - 각 마을 별 받는 박스 개수를 기록하는 1차원 int형 배열 1. M개의 보내는 박스 정보를 입력받아 객체 배열에 저장한다. info = new Info[M + 1]; for(int i = 1 ; i = now.box) { for(int j = now.from ; j < now.to ; j++) { capacities[j..

📖 문제 14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파 www.acmicpc.net 💡 풀이 방식 • 다익스트라 (우선순위 큐) 최단 경로인 지점을 항상 우선으로 탐색하고자 점프 횟수 기준 오름차순 정렬하는 우선순위 큐를 활용한다. class Node implements Comparable { int x, y, w; public Node(int x, int y, int w) { this.x = x; this.y = y; this.w = w; } @Override public int compareTo(Node n) { // 💥 ..

📖 문제 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 1 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 💡 풀이 방식 • 정렬 + 그리디 + 중간값 우체국 위치와, 마을 거주 인원을 저장하는 마을 객체를 만든다.마을 객체 배열에 값을 입력받고, 모든 마을의 인원 수를 저장한다. 입력받은 마을 객체 배열을 정렬한다. - 서로 거리가 같은 경우, 마을 인원 수 기준 오름차순 정렬 - 서로 거리가 다르다면, 거리 기준 오름차순 정렬 그리고 완전탐색을 통해 하나씩 인구 수를 계산하..

📖 문제 1987번: 알파벳 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 www.acmicpc.net 💡 풀이 방식 • 백트래킹 + DFS (0,0)부터 dfs를 한다. 해당 점의 인접한 4방향 탐색을 통해 격자 범위 내에 있고, 지금까지 나온 적 없는 알파벳인 경우 마저 탐색을 진행하며 최대 경로를 찾는다. 🔺 코드 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 ..

📖 문제 1455번: 뒤집기 II 세준이는 동전 뒤집기를 하려고 한다. 세준이는 동전을 N×M개 가지고 있다. 동전은 세로로 N개, 가로로 M개 크기의 직사각형에 차곡차곡 놓여져 있다. 동전의 앞면을 0이라고 하고 뒷면을 1이라고 www.acmicpc.net 💡 풀이 방식 • 그리디 (i,j) 위치에서 뒤집는 경우, 해당 칸의 왼쪽 칸과 위쪽 칸이 뒤집힌다 그러므로 오른쪽 아래 점부터 위로 올라가면서 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 import java.util.*..

📖 문제 10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이 www.acmicpc.net 💡 풀이 방식 • BFS . 모래성이 없는 노드를 중심으로 생각한다! 모래성이 없는 노드의 주변 8방향 노드 中 모래성이 있는 노드의 튼튼함을 하나 깎는다. 그러다 보면 결국 가운데 모래성이 없어지게 되는데, 이 때는 그 위치를 노드에 추가해주면 된다. 💥 유의사항 이미 한 번 확인한 모래성이 없는 노드는 다시 확인할 필요가 없기 때문에 새롭게 모래성이 없어진 노드만 탐색한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 1..

📖 문제 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 💡 풀이 방식 • BFS 필요 자료구조 - 로봇 객체 (행, 열, 방향, 명령 횟수) - 3차원 boolean형 방문 표시 배열 : [행][열][방향] ⭐ - dx/dy 배열 동서남북 배열 1. 격자를 입력받는다. 2. 시작점 위치,방향과 도착점 위치,방향을 입력받는다. String[] s1 = br.readLine().split(" "); start = new Robot(Integer.parseInt(s1[0]) -1, Integer.parseInt(s1[1])..

📖 문제 5547번: 일루미네이션 첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는 www.acmicpc.net 💡 풀이 방식 • BFS 외벽과 닿는 모든 면을 정육각형으로 돌리기 위해 격자 판 숫자를 저장할 map 배열과, 벽 개수를 저장할 2차원 배열 result의 크기는 [행+2][열+2]로 설정한다. map = new int[H+2][W+2]; // 외벽과 닿는 모든 면을 정육각형으로 돌리기 위해 +2 result = new int[H+2][W+2]; // 벽 개수 저장 리스트 visited = new boolean[H+2][..