begong블로그

다이나믹 프로그래밍 문제 입력 받는 방법이 괴랄해서 문제이지 풀이 자체는 어렵지 않다. dp[T][N+2] 배열을 만든다 여기서 T는 주사위를 굴린 횟수, N+2는 시작점, 끝점을 포함한 칸의 개수이다. 주사위를 n번 굴렸을때 도달할 수 있는 지점에서 획득할 수 있는 코인의 최대치를 구한다. 구하는 방법은 주사위를 n-1번 굴렸을때, 주사위의 눈 s가 나와서 현재의 지점에 도달했다고 가정하는 것이다. (그래서 3중 반복문이 쓰인 것이다) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main{ public stati..

다이나믹 프로그래밍 문제이다. 하나의 조건에만 집중에서 풀면 쉽게 풀린다. n번째 집과 n+1번째 집의 색깔만 안겹치면 된다. Blue Red Blue, Red Blue Green 등 모두 상관없다. 따라서 n+1번째 집을 Red로 칠하고 싶다면 n번째집의 Blue Green중 작은 값을 가져와 Red를 칠하는 비용을 더해주면 된다. Red, Blue, Green 모두 칠하는 경우를 기록해놓고 반복해주면 dp 배열의 마지막에 모든 집을 칠하는 비용의 경우가 나오고 거기에서 최소값을 구해주면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays;..

Stack을 활용하는 문제 한 방향으로만 건물을 볼수있다 => 이미 앞에있는 건물들은 신경안써도 된다. 이미 stack안에 존재하는 건물들이 새로 들어온 건물을 볼수 있냐 없냐에만 신경쓰면됨 => 이미 stack에있는 건물보다 큰 건물이 들어왔을때는 stack에서 제거 : stack에 있는 건물들은 이 건물을 볼 수 없기 때문에 => stack에 있는 건물보다 작은 건물이 들어왔을때 : stack에 push 이 로직으로 진행한다면 stack안에는 새로 들어오는 건물을 볼 수 있는 건물만 남게 된다. 새로 들어온 건물을 몇개가 볼수있느냐? 로 이해하면 금방 풀리는 문제 단 건물의 크기가 10억까지 존재함으로 long타입을 써야 overflow가 나지 않는다. import java.io.BufferedRea..

증가하는 가장 긴 수열 응용 문제 다른 문제들과 다르게 이 문제에서는 증가하다가 피크를 찍고 다시 감소하는 부분까지 수열이 이어진다. 내가 생각해 낸 방법은 앞에서부터 증가하는 수열, 뒤에서부터 증가하는 수열을 구해서 한 점에서 만나면 된다. 각각 구한후 두개를 더한 최대값을 찾으면 답이 구해진다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buffer..

기본적인 증가하는 가장 긴 수열 문제 조건이 맞을 때, 앞에서 계산한 것 중 가장 큰 것을 가져와 +1해주면 되는 문제이다. 이 문제에서는 증가가 아닌 감소하는 수열을 구하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseI..

해당 케이스들의 답을 적어놓으면서 풀면 쉽게 풀리는 문제 점화식이 피보나치 수열의 패턴을 따라가는 것을 볼 수 있다. 원리를 추측하자면 Dp[n]에서 처음 두명이 악수를 하는 경우 : Dp[n-2] DP[n]에서 처음 두명이 악수를 안하는 경우 : Dp[n-1] 따라서 Dp[n] = Dp[n-1]+Dp[n-2] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; class Main{ /* 1 = 1 2 = 2 3 = 3 4 = 5 5 = 8 => 피보나치 수열이다 */ public static void main(String[] args) throws IOException { BufferedR..

dp라고 적혀있긴 하지만 사실상 그래프 탐색 문제 Dp라고 할만한 요소는 이미 탈출을 경험했던 경로를 저장하여 (dfs 함수의 마지막 부분) 탈출을 경험했던 경로에 들어서면 탐색을 멈춤으로써 시간을 절약하는 것이다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main { //u,r,d,l static int direction[][] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; static boolean success[][]; static int map[][]; static int visit..