본문 바로가기

분류 전체보기

 (215)
백준 1516 게임 개발 (Java) 1. 문제 링크 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 위상정렬을 이용해서 푸는 문제이다. 진입 차수를 이용해서 큐에 넣는 타이밍을 정한다. dp를 이용해 더 큰 경우를 저장한다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; ..
백준 16916 봄버맨 2 (Java) 1. 문제 링크 16919번: 봄버맨 2 첫째 줄에 R, C, N (1 ≤ R, C ≤ 200, 1 ≤ N ≤ 109)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 규칙이 있는 문제이다. (N이 1인 경우를 제외하고는) 4의 배수로 규칙이 발견되는데 N 나누기 4의 나머지에 4를 더한 값이 N이 된다. N이 되기 전까지 폭탄을 설치하고 시간 체크하고 폭발하는 폭탄을 전부 큐에 넣어두고 시간을 체크한다. 여기서 폭탄을 큐에 넣는 이유는 폭탄이 모두 동시에 폭발하기 때문이다. 폭발은 큐에 넣은 것들을 하나씩 빼면서 방문 여부에 체크를 해준다. 4. 코드 import j..
백준 2589 보물섬 (Java) 1. 문제 링크 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 최단 거리 중 가장 먼 거리를 찾는 것이다. (뭔가 말이 이상하지만) bfs로 나온 거리들 중 가장 돌아서 가는 경우를 찾으면 된다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java.io.IOException; pub..
백준 1309 동물원 (Java) 1. 문제 링크 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 조금 잘 생각해야 하는 dp문제였다. dp[i-1]에 사자가 왼쪽, 오른쪽 있다는 생각으로 dp[i-1]*2에 dp[i-2]를 더했다. 나머지 연산을 한 상태로 dp에 저장해야 한다. 점화식: dp[i] = (dp[i-1]*2 + dp[i-2]) % 9901 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) t..
백준 1715 카드 정렬하기 (Java) 1. 문제 링크 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. A와 B를 합치려면 A+B번 비교해야 한다. 2. 작은 숫자 2개를 뽑아서 합치는 과정을 반복하면 된다. 3. PriorityQueue를 이용해서 2개를 뽑고 합을 다시 넣어서 다른 비교에 사용하도록 했다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.PriorityQueue..
백준 3055 탈출 (Java) 1. 문제 링크 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 고슴도치는 물이 찰 예정인 곳으로 갈 수 없기 때문에 먼저 물을 채우는 방향으로 진행했다. 물을 채우고 bfs 탐색을 하면 고슴도치가 갈 수 있는 곳을 큐에 넣는다. 큐가 비었는데도 도착하지 못했다면 KAKTUS를 출력한다. 4. 코드 import java.awt.List; import java.io.BufferedReader; import java.io.IOException; import java.io.InputSt..
백준 1600 말이 되고픈 원숭이 (Java) 1. 문제 링크 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 bfs로 탐색하는 문제이다. K번까지 움직일 수 있다고 정해져있기 때문에 좌표에 도착했을 때 몇번째로 도착했는지까지 생각해서 visit을 3차원 배열로 했다. 말의 움직임을 따랐을 때 움직임의 횟수를 증가하고, 원숭이의 움직임인 4방탐색의 경우에는 움직임의 횟수를 그대로 둔 상태로 이동한다. 4. 코드 import java.io.BufferedReader; import java.io.Inp..
백준 14499 주사위 굴리기 (Java) 1. 문제 링크 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 주사위 6면을 한 번에 다루면서 숫자를 옮겼다. 주사위가 떨어지는 1 2 3 4 방향에 따라 주사위 6면 전부를 움직였다. 주사위 배열은 상단, 하단, 동, 서, 남, 북 순으로 조작했다. 입력받은 명령에 따라 주사위에서 바꾸는 4부분의 값의 바꿨다. 도착한 바닥이 0이면 바닥에 주사위 하단의 숫자를 바닥에 넣는다. 도착한 바닥이 숫자라면 주..

티스토리툴바