in.add()

문제 링크 : https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 문제 해결 방법 섬에 번호를 매기기 위해 BFS. 섬마다 최소 길이로 놓을 수 있는 다리를 찾기 위해 DFS. 마지막으로 크루스칼로 MST를 구해줬다. import java.util.*; public class Main { static int N, M, islandCnt, answer, answerCnt; static int[][] map, dist; stati..

문제 링크 : https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 문제 해결 방법 14002번과 같은 문제이지만 입력 크기가 훨씬 커서 이진 탐색을 이용한 LIS를 구현했다. import java.util.ArrayList; import java.util.Deque; import java.util.LinkedList; import java.util.Scanner; public class Main { public sta..

문제 링크 : https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 해결 방법 DP를 이용한 LIS알고리즘으로 구현했다. import java.util.Deque; import java.util.LinkedList; import java.util.Scanner; public class Main { public static void main(String[] args..

문제 링크 : https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 해결 방법 1행부터 내려가면서 위의 행의 같은 열이 아닌 최솟값을 더해줬다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[][] hou..

문제 링크 : https://www.acmicpc.net/problem/2116 2116번: 주사위 쌓기 첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 www.acmicpc.net 문제 해결 방법 0번 Dice의 각 side를 bottom으로 한 모든 경우의 최댓값을 찾아줬다. import java.util.ArrayList; import java.util.Scanner; public class Main { static class Dice { int idx; int[] side; public Dice(int idx, int[] side) { this.idx = id..

문제 링크 : https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 문제 해결 방법 정렬하면 어떻게 해볼 수 있지 않을까 싶어서 정렬 후 index - 배열[index]로 차이를 구했고 차를 모두 더해서 출력했다. 한 개뿐인 테스트 케이스는 통과했지만 제출하니 실패해서 오래 고민했다. N이 최대일 때 모두가 예상 등수를 1로 하는 경우가 있다면 int 범위를 넘어가기 때문이었다. 차의 합을 구하는 dif 변수를 int에서 long으로 바꿔 성공할 수 있었다..

문제 링크 : https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 문제 해결 방법 완전 탐색으로 오른쪽 사탕과 바꿨을 때, 아래 사탕과 바꿨을 때 최대 연속된 개수를 구하는 방법으로 구현했다. import java.util.Scanner; public class Main { static char[][] candies; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); candies = new char[N][N]; sc.nextLine();..

문제 링크 : https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 해결 방법 bfs로 구현했다. 입력을 받으면서 map배열의 아기 상어의 초기 위치를 0으로 바꿔주는 것을 놓쳐서 오래 걸렸다.. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int N, fishX, fishY, minDist, ..