본문 바로가기

ALGORITHM

 (212)
백준 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. 문제 풀이 메모리 제한이 있어서 최대한 입력받으면서 풀려고 했다. 처음 입력받은 줄을 배열에 저장한다. 비교 범위에 있는 값들 중 큰 값과 입력받은 값을 더해 저장한다. 저장된 값들 중 최솟값과 최댓값을 찾는다. ++++ 최솟값과 최댓값을 찾기 위한 배열을 따로 만들어야 했다. 최댓값이나 최솟값을 찾는 과정에서 비교하고 더하는 값의 위치를 잘못 생각했었다. 손으로 그리면서 확인할 때는 다음 줄의 값들과 비교했는데 그렇게 하니까 이..
백준 11559 Puyo Puyo (Java) 1. 문제 링크 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 전체 맵에서 뿌요가 있으면 bfs를 돌면서 4개 이상이 모일 경우 없앤다. 없애고 나면 전체에서 없어진 뿌요들 자리를 아래로 밀어서 채운. 없앨 뿌요가 없으면 반복을 중단한다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util..
백준 10816 숫자 카드 2 (Java) 1. 문제 링크 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 map에 숫자 카드에 적힌 정수와 개수를 넣는다. containsKey()를 이용해서 입력받은 수가 map에 들어있는지 확인하고 출력한다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; impo..

티스토리툴바