네발로 코딩하는 포메라니안

문제 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 과정 왼쪽, 왼쪽의 대각선, 위쪽에서 제일 작은 정사각형 크기 + 1이 현재 노드에서의 정사각형의 크기로 한다. 자신보다 아래에 위치한 1들은 나중에 고려하므로 생각하지 않는다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args)..

문제 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 풀이 과정 dp[i] = (dp[i-1][x] + dp[i-1][1] + dp[i-1][2]) + (dp[i-1][x] + dp[i-1][2]) + (dp[i-1][x] + dp[i-1][1]) = dp[i-1]*2 + dp[i-1][x] = dp[i-1]*2 + dp[i-2] import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception..

1. 문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 2. 풀이 과정 [방법1] PriorityQueue를 이용한 BFS 도착 지점이 출발 지점보다 작은 경우, 빼기만 해서 가는 것이 가장 빠르므로 N-K를 출력한다. 아닌 경우는 PriorityQueue를 써서, 현재 최소 경로인 값에 +1, -1, *2 를 해본다. 더보기 import java.io.BufferedReader; import java.io..

1. 문제 https://www.acmicpc.net/problem/14722 14722번: 우유 도시 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후 www.acmicpc.net 2. 풀이 과정 배열의 크기가 1000x1000이므로, DFS와 같은 완탐으로는 시간 초과가 날 것 같아서 DP로 시도했다. 아직 DP문제는 푸는 데 시간이 좀 걸린다.. 딸기 우유, 초코 우유, 바나나 우유 3가지 경우를 나눠서 생각하기 위해서 DP를 3차원 배열로 구현했다. 중간에 안 먹고 건너 뛸 수도 있어서 마지막에 어떤 종류를 먹었는지를 고려해주기 위해서다. 전체 배열을 2차원 배..