본문 바로가기

백준32

BOJ 8972 - 미친 아두이누(Java) https://www.acmicpc.net/problem/8972 8972번: 미친 아두이노 요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. www.acmicpc.net 풀이 플레이어의 이동 명령만큼 1~6을 반복, 미친 아두이노와 플레이어 아두이노가 겹치면 게임 종료 1. 종수(플레이어) 이동 2. 이동 횟수 ++ 3. 플레이어가 죽었는지 확인 4. 미친 아두이노 이동 5. 플레이어가 죽었는지 확인 6. 겹치는 미친 아두이누 폭발 미친 아두이노의 위치 정보를 2차원 배열 List와 List를 이용해 관리 static List[][] map; static Lis.. 2022. 1. 14.
BOJ 23289 - 온풍기 안녕(Java) https://www.acmicpc.net/problem/23289 23289번: 온풍기 안녕! 유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기 www.acmicpc.net 풀이 조사하는 칸(배열 입력 칸이 5인 칸)이 모두 K 이상일 때까지 1~3 반복후, 초콜릿의 갯수를 출력 1. 모든 온풍기에서 바람이 나옴 온풍기의 방향에 따라 온도가 확산 하나의 좌표에서 온풍기의 방향에 따라 3방향으로 확산 중첩되는 좌표의 경우 한번만 계산 2. 온도 조절 상하좌우 인접한 칸을 조사, 온도가 높은 칸은 온도를 줄이고 낮은 칸은 온도를 높임 이는 모든 칸에서 한번에 실행됨 3... 2022. 1. 12.
BOJ 20058 - 마법사 상어와 파이어 스톰(Java) https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 풀이 1. 명령의 수 만큼 반복, 명령 L에 대해 진행 1) 2L X 2L로 구역 나누기, 구역 별 회전 2) 인근 지역에 얼음이 없다면 얼음줄이기 - 동서남북 4방향에 대해 얼음이 남은 인접 칸의 개수 확인 - 인접 칸의 개수가 3이상이 아니라면 해당 칸의 얼음을 1 줄임 2. 1이 끝나면 남아있는 얼음의 합, 전체 영역 중 가장 큰 덩어리를 탐색 명령 L에 따른 구역 나누기.. 2022. 1. 8.
BOJ 16985 - Maaaaaaaaaze(Java) https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 풀이 1. 2가지를 기준으로 모든 경우의 수를 탐색 1) 판의 회전(어느 판을 얼만큼 회전할지) 2) 회전을 완료한 5개의 판 쌓기 2. 위의 기준으로 만든 3차원 행렬을 bfs 거리 탐색 몇번째 판이 몇도 회전하는지 각 판마다 몇 도 회전하는지 모든 경우의 수를 탐색 - 현재 판을 90도 회전 시키고 다음 판에 대해 재귀 호출 5번째(마지막)판에 대한 결정이 끝나면 판을 쌓.. 2022. 1. 6.
BOJ 1202 - 보석 도둑(Java) https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 완전 탐색으로 풀 경우 보석의 개수 N(1 ~ 300,000), 가방의 개수 M(0 ~ 100,000,000)으로 O(N*M)의 시간 복잡도를 가짐, 안될 거라 생각하고 풀어봤지만 역시나 시간초과 발생 * 시간 복잡도를 줄여야하며 우선순위 큐를 이용하여 품 우선 순위 큐를 이용한 풀이 - 가방에 대해서는 for문을 이용하여 탐색 -.. 2021. 12. 31.
BOJ 1715 - 카드 정렬하기(Java) https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 이전의 합이 누적되는 형태 - (a + b) + (a + b + c) + (a + b + c + d) + ...... - 각 합의 작은 값이 누적되는 횟수를 크게, 큰 값이 누적되는 횟수를 작게 해야함 불가능한 방법 입력 요소의 정렬 만으로는 해결 불가능 - ex) 60, 50, 70, 80 - 요소 정렬 : 50, 60, 70, 80 - 누적 합 -> (50 + 60) + (.. 2021. 12. 27.
BOJ 4256 - 트리(Java) https://www.acmicpc.net/problem/4256 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 풀이 전위 순회 : 현재 노드 -> 왼쪽 노드 -> 오른쪽 노드 중위 순회 : 왼쪽 노드 -> 현재 노드 -> 오른쪽 노드 * 전위 순회의 0번째 노드는 현재 노드, 중위 순회 요소에서 현재 노드를 기준으로 왼/오른쪽 노드로 나뉨 위의 2가지 순회로 트리 구조 및 후위 순회 파악 가능 now= 0을 루트로 [0 ~ N]의 범위에 대해 탐색 1. preOrder[now] = 현재 노드 2.. 2021. 12. 23.
BOJ 23291 - 어항 정리(Java) https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 풀이 물고기 수의 최대/최소인 어항의 차이가 K이하일 때 까지 반복 1. 물고기가 최소인 어항에 물고기 추가 - 어항에 물고기 수가 최소인 어항들에 물고기 수를 1씩 추가 2. 어항 쌓기 - 시계 방향 90도로 어항을 말아서 쌓음 - 처음에는 가장 왼쪽의 1개 항만 이동, 이후부터는 쌓여져있는 모든 어항을 이동 3. 물고기 수 조절 - 상하좌우 인접 어항을 확인, 현재 어항이 인접한 어항의 물고기.. 2021. 12. 22.
BOJ 2638 - 치즈(Java) https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 매 시간마다 외부 공기와 2변 이상 접촉하면 해당 위치의 치즈가 녹음 외부 공기 판별 가장자리에는 치즈가 없다. -> 모든 가장자리는 외부 공기 (0, 0)의 위치로 부터 시작 해서 치즈를 만나지 않는 위치로 dfs 탐색을 이용하여 외부 공기 판별 가능 private static void checkExternalAir(int i, int j) { visit[i][j] = true.. 2021. 12. 20.

티스토리툴바