Dev.baelanche

너무 쉬운 dp문제이긴 한데, dp문제는 모두 포스팅하기로 정해서 올린다. 문제에 써있는대로 탑다운 방식으로 풀었다. n, m에서 왼쪽, 왼쪽위, 위 방향으로 이동하면서 1, 1에 도착했을때의 개수를 더해주었다. public class Main { static long dp[][]; public static long dp(int n, int m) { if(n == 0 || m == 0) return 0; if(n == 1 && m == 1) return 1; if(dp[n][m] != -1) return dp[n][m]; long result = (dp(n, m-1) + dp(n-1, m) + dp(n-1, m-1))%1000000007; dp[n][m] = result; return result; } ..

완전탐색으로 풀기엔 주어진 시간이 너무 짧다. 사탕배열을 만들어 사탕이 있는지 여부를 저장해놓고 DP배열로 매 탐색마다 최대로 먹을수 있는 사탕의 개수를 갱신한다. public class Main { static boolean a[][]; static int dp[][]; public static int findCandy(int x, int y, int m) { if(x == 301 || y == 301) return 0; if(m == 0) return 0; if(dp[x][y] != -1) return dp[x][y]; if(a[x][y]) dp[x][y] = m; else dp[x][y] = 0; dp[x][y] += Math.max(findCandy(x+1, y, m-1), findCandy(x,..

DP문제 RGB거리와 상당히 유사한 문제이다. 배열의 n-1번째부터 0번째까지 반대 방향으로 진행하면서 최고합, 최소합을 메모이제이션 하면서 구하면된다. n이 최대 100000이라 DP로 그냥 풀리긴 하지만 메모리 제한을 보니 슬라이딩윈도우 기법을 요구하는 듯하다. 슬라이딩 윈도우는 일정한 구간을 훑으며 진행하는 기법이다. 글로 표현하면 뭔가 있어 보이는데, 배열 크기를 1로 만들어서 이전 배열에서 연산한것을 갱신만 해주면 된다. colMax, colMin 은 최대합, 최소합 배열이고 tempMax, tempMin 은 이전계단의 값이다. colMax, colMin 배열에 tempMax, tempMin의 값을 연산을 통해 업데이트 시켜주면 된다. public class Main { public static..

처음에는 DFS + 완전탐색으로 풀었는데 당연히 시간초과가 났다. 틀린소스 (타임아웃) public class Main { static int n; static int m; static int a[][]; static int dx[] = {0, 1}; static int dy[] = {1, 0}; static int max = 0; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st = new StringTokenizer(br.readLine()); n = Integer.parseI..

작년에 카카오 모의테스트에서 이와 똑같은 문제가 나온적이 있었다. 당시에 dp 문제를 하나도 풀 줄 몰랐는데 신기하게도 이건 술술 풀렸다;; 1. 입력받은 대로 2차원 배열을 채운다. 2. 정사각형의 조건을 만족하려면 가로, 세로의 길이가 같고 인접한 배열을 모두 1이어야 하므로 좌측 위, 좌측, 위의 값이 모두 1 이상이어야 한다. 3. 메모이제이션 기법으로 큰 정사각형의 크기를 누적시키며 진행한다. a[i][j] = min(a[i-1][j-1], a[i-1][j], a[i][j-1]) + 1; 2번을 풀어쓰면 위 식과 같겠다. public class Main { public static void main(String[] args) throws Exception { BufferedReader br = ..

n이 최대 20이라 문제에 나와있는 점화식을 가지고 재귀하여 풀면 된다. 나는 굳이 탑다운 방식으로 풀었다. public class Main { static int dp[]; public static int f(int k) { if(k == 0) return 0; if(k == 1) return 1; if(dp[k] != -1) return dp[k]; int ret = f(k-1) + f(k-2); dp[k] = ret; return ret; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); dp = new int[n+1]; Arrays.fill(dp, -1); Syste..

LIS 문제이다. 가장 큰 증가하는 부분 수열 문제와 답만 다를뿐 로직이 동일하다. 가장 긴 감소하는 부분 수열에 간단하게 풀이를 서술했다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a[] = new int[n]; int dp[] = new int[n]; for(int i=0; i

백준 문제중 스티커를 먼저 푼 적이 있는데, 그 문제와 유사하다. 사자는 가로 혹은 세로로 연속된 우리에 놓을 수 없기 때문에 우리에 놓을 때 이전 우리의 상태를 파악해야 한다. 우리의 상태는 0(사자가 없음), 1(좌측에 사자를 둠), 2(우측에 사자를 둠) 으로 구분했다. 0 일때 1, 2 에 1 일때 0, 2 에 2 일때 0, 1 에 사자를 배치할 수 있다. 탑다운 방식으로 짰다. public static int lion(int n, int status) { if(n == N) return 1; if(dp[n][status] != -1) return dp[n][status]; int ret = lion(n+1, 0) % 9901; if(status != 1) ret += lion(n+1, 1) % ..