백준

빙산 - 2573번

풀이 방법 dfs를 사용한 방법을 생각했다. 모두 다 이어져 있으면 다시 1년 지나게 하고 이어져 있지 않으면 종료하기 위해 먼저 빙산을 녹이는 함수를 작성했다. 주변을 비교해서 녹이면 되는 함수이다. dfs는 check 배열을 만들어서 위치를 갔었는지 체크하고 0이 아닌 아무 곳에서 시작했다. 동서남북으로 확인하면서 가능한 경로인지 확인하고 연결되어 있는 갯수를 반환하게 했다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static int N; static int M; static int[][] array; static int x, y; static boolean[][] check; public ..

크게 만들기 - 2812번

풀이 방법 스택을 사용해서 앞에서부터 넣어주면서 지금 넣는 자릿수가 앞의 자릿수보다 크면 제거하는 방법을 사용했다. 출력할땐 N-K개 까지만 출력해서 자릿수를 맞춰서 출력해주었다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseI..

짐 챙기는 숌

풀이 방법 책이 무조건 차례대로 들어가기 때문에 if문을 사용해서 차례대로 비교해주면서 넣어주면 된다. N이 0일땐 StringTokenizer를 생성하면 nullpointer 오류가 나기 때문에 그 점만 주의하면 된다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine());..

돌다리 건너기 - 2602번

풀이 방법 먼저 재귀적으로 완전탐색을 이용해서 풀었다. 하지만 시간초과가 나오고 말았다. 그래서 DP를 추가해 주었다. DP는 [현재 밟은 곳][찾고 있는 문자 인덱스][돌다리 종류] 로 나타내었다. 예제 입력 3번을 예로 들자면 GGGGRRRR GGGGRRRR GGGGRRRR GGGGRRRR SSSSGGGG SSSSGGGG SSSSGGGG SSSSGGGG 이렇게 찾은 후 다음 G에서 GGGGRRRR GGGGRRRR GGGGRRRR GGGGRRRR SSSSGGGG SSSSGGGG SSSSGGGG SSSSGGGG 똑같이 반복 될것이다. 그래서 위쪽의 돌다리에서 3번째 G를 밟은 후 현재는 아래쪽의 처음 나오는 G를 밟고 있으면 현재 밟은 곳에서 찾고 있는 문자가 인덱스와 돌다리의 종류가 같은 케이스가 나온..

괄호 제거 - 2800번

풀이 방법 각 괄호의 경우의 수를 구하기 위해 조합을 뽑아냈다. 먼저 괄호의 인덱스를 map에 저장해주고 그 인덱스르 바탕으로 조합의 경우의 수를 계산했다. 경우의 수를 바탕으로 괄호를 제거하고 출력해 주었다. 재귀 함수로 조합을 계산할 수 있다. (((0)))

듣보잡 - 1764번

풀이 방법 contains의 시간복잡도가 list보다 set이 좋아서 먼저 hashset에 듣도 못한 사람을 넣어주고 보도 못한 사람을 contains으로 확인 후 있으면 list에 넣어주었다. 출력할 때는 sort를 이용해서 사전순으로 정렬 후 출력했다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringToken..

징검다리 건너기 - 21317번

풀이 방법 다이나믹 프로그래밍을 사용해서 풀이했다. 중요한 게 매우 큰 점프를 한번만 사용할 수 있다는 것이다. 그래서 매우 큰 점프를 사용할 수 있는 모든 경우의 수에 넣어주었다. 나머지는 DP의 Bottom-Up 방식으로 풀이하면 된다. 내 코드 package com.company; import java.io.*; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String..

스티커 - 9465번

풀이 방법 DP의 Bottom-Up 방식을 이용해서 풀이했다. 맨앞의 스티커 두개를 먼저 넣어주고 다음 스티커부터 대각선방향으로 더한 값과 서로 변을 공유하는 스티커 중 더 큰값을 찾아주었다. 내 코드 package com.company; import java.io.*; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTo..

뒤집기 II - 1455번

풀이 방법 a, b칸을 뒤집으면 하위 모든 칸들이 뒤집히기 때문에 맨 위에서부터 확인해서 뒤집어 주었다. 세로와 가로 둘다 줄여 나가는것이 아닌 한쪽만 기준으로 잡고 줄여나가도 된다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.pars..

알바생 강호 - 1758번

풀이 방법 최대로 팁을 받기 위해서는 내림차순으로 정렬해서 더해주면 된다. tip의 타입을 int가 아닌 long으로 선언해주는 것만 주의하면 된다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); Integer array[] = new Integer[N]; Long tip = 0L; for (i..