본문 바로가기

분류 전체보기

 (215)
백준 2636, 2638 치즈 (Java) 1. 문제 링크 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 입력받으면서 전체 치즈의 수를 셌고 치즈가 다 녹으면 끝이 난다. find()로 DFS 하면서 외부 좌표는 out 배열에 저장했다. 외부 좌표를 다 찾았으면 melt로 치즈를 녹인다. melt()에서는 치즈가 나오면 out 배열의 값을 비교해서 두 변 이상이 외부에 노출되었다면 queue에 넣는다. (2638번) melt 끝나고 오면 전체 치즈 수에서 큐의 크기를 빼고, 큐에서 빼서 현 좌표를..
백준 12865 평범한 배낭 (Java) 1. 문제 링크 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 전형적인 DP 문제이다. 해당 무게가 되는지 여부를 알고 지금 물건의 가치가 더 높은지 판단해서 저장한다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static..
백준 2206 벽 부수고 이동하기 (Java) 1. 문제 링크 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 2. 문제 및 입출력예제 +) 반례 테스트케이스 모았습니다. 참고하세요~ 더보기 2 4 0111 0010 ans: 5 --- 2 4 0111 0110 ans: -1 --- 1 1 0 ans: 1 --- 5 8 01000000 01010000 01010000 01010011 00010010 ans: 20 --- 6 7 0000000 0111111 0100010 0101010 0101010 0001010 ans: 12 ---..
백준 21318 피아노 체조 (Java) 1. 문제 링크 21318번: 피아노 체조 피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 악보 난이도를 입력받으면서 앞의 난이도보다 낮은 경우 값을 1만큼 추가한다. dp로 값을 누적하면서 배열에 저장하고 입력 받은 곡 사이 값의 차이를 출력한다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void ..
백준 10775 공항 (Java) 1. 문제 링크 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 서로소 집합을 이용했다. 입력 받고 그 게이트를 기준으로 도킹할 위치를 찾고 그 위치가 0이 되면 더이상 도킹할 수 없는 상태이다. 도킹할 위치를 찾으면 해당 위치와 그 앞을 도킹(합)한다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impo..
백준 2573 빙산 (Java) 1. 문제 링크 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 입력받고 종료 조건이 될 때까지 반복문을 돈다. 처음에 덩어리 개수를 구하는데 0이거나 2보다 커지면 탈출한다. 그리고 빙산 기준으로 사방탐색을 해서 바다와 닿은 면적을 계산한다. 3-1. 바로 녹이지 않고 큐에 담아둔다. 3-2. 모든 빙산을 다 녹였다면 큐에 넣어둔 녹은 빙산을 map에 적용한다. 시간을 증가하고 반복문을 계속한다. 4. 코드 import java.io.BufferedReader;..
백준 1149 RGB 거리 (Java) 1. 문제 링크 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 DP 문제라서 겁먹었는데 전에 풀었던 2096 내려가기랑 비슷한 느낌이었다. 앞의 값 중 작은 것을 골라 현재 위치에 있는 값과 더한다. 여기서 앞의 값은 1이면 (2,3) 2면 (1,3), 3이면 (1,2) 중 하나를 고르는 것이다. 앞에 있는 값들 중 제일 작은 값을 더해가면서 마지막 줄에서 3개 중 최솟값을 출력한다. 4. 코드 import java.io.BufferedReade..
백준 2096 내려가기 (Java) 1. 문제 링크 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 메모리 제한이 있어서 최대한 입력받으면서 풀려고 했다. 처음 입력받은 줄을 배열에 저장한다. 비교 범위에 있는 값들 중 큰 값과 입력받은 값을 더해 저장한다. 저장된 값들 중 최솟값과 최댓값을 찾는다. ++++ 최솟값과 최댓값을 찾기 위한 배열을 따로 만들어야 했다. 최댓값이나 최솟값을 찾는 과정에서 비교하고 더하는 값의 위치를 잘못 생각했었다. 손으로 그리면서 확인할 때는 다음 줄의 값들과 비교했는데 그렇게 하니까 이..

티스토리툴바