IT_공부하자

[JAVA] 백준 2688 줄어들지 않아_DP

문제 :https://www.acmicpc.net/problem/2688  접근 :   - n = 1,  dp[1] = 10, before = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}  - n = 2, dp[2] = 10 - 0 + 10 - 1 + 9 - 1 + · · · + 2 - 1 , before = {0, 10, 9 ,  8, 7, 6, 5, 4, 3, 2, 1}  - n = 3, dp[3] = 55 - 0 + 55 - 10 + 45 - 9 + · · · + 2 - 1, before = {0, 55, 45,  36, 28, 21, 15, 10, 6, 3, 1} 즉 dp[n] = dp[n-1] - before[0] + (dp[n-1] - before[0]) - before[1]..

백준 9465 스티커_DP

문제 : https://www.acmicpc.net/problem/9465  접근 :   - 위쪽을 뜯는 경우와 아래쪽을 뜯는 경우를 나눠서 생각한다.  - 가로의 위치가 0 과 1 인 경우에는 나올 수 있는 최대값을 dp에 저장한다.  - 가로의 위치가 2 이상인 경우에는 위쪽과 아래쪽을 나눠서 현재 위치까지 도달했을 때, 가능한 최대값을 dp에 저장한다.  - 가로로 진행할 때, 항상 위쪽과 아래쪽을 나누어 더 큰 값으로 ans 값을 갱신한다.  - n-1 까지 진행한 후, ans 값을 출력한다.       코드구현 :  import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public clas..

[JAVA] 백준 1520 내리막길_DP

문제 :https://www.acmicpc.net/problem/1520  접근 1:   - BFS 로 결과 지점까지 도달하면 결과값 + 1  - Queue 가 빌 때까지 실행 후 출력  - 메모리 초과로 불가  접근 2:  - DP 와 DFS 를 이용하여 정답을 카운트  - 정답 지점까지 도달한 후, 시작 지점으로 돌아오면서 count 를 증가  - 시작 지점에 도달하면 count를 정답으로 출력  코드 구현 : import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { private static int[][] map; private static int[]..

[JAVA] 백준 2193 이친수_DP

문제:https://www.acmicpc.net/problem/2193  접근 :   - 1자리 수의 경우 = 1  - 2자리 수의 경우 = 10  - 3자리 수의 경우 = 100, 101  - 4자리 수의 경우 = 1000, 1010, 1001  - 5자리 수의 경우 = 10000, 10100, 10010, 10001, 10101  - n자리 수의 경우 = n-1 자리 수의 경우 + 0, n-2 자리수의 경우 + 01    -> DP[n] = DP[n-1] + DP[n-2]  코드 구현 : import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public ..

[JAVA] 백준 2156 포도주_DP

문제 : https://www.acmicpc.net/problem/2156  접근 :   - 마지막 포도주를 마시는 경우와 마시지 않는 경우를 나눈다.  - 만약 마지막 포도주를 마시지 않는 경우, 1) 이전까지(n-1)의 최대값이 정답이다.  - 마지막 포도주를 마시는 경우, 2) 3번째 전(n-3) 최대값에 전 포도주 잔(n-1)과 이번 포도주 잔(n)을 마실 수 있다.  - 또한, 3) 2번째 전(n-2) 최대값에 이번 포도주 잔(n)을 마실 수 있다.  - 1) 2) 3) 3가지 경우 중 최대값을 정답으로 출력한다.    코드 구현 :import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;pu..

문제:https://www.acmicpc.net/problem/2011  접근 :   - 0 으로 시작하는 숫자가 들어오면 복호화가 불가능 하므로 0을 출력한다.  - 길이가 2이상인 경우에는 복호화 한 수가 26 이하이면 2, 6 개별 수 및 26 합친 수의 경우 모두를 고려한다.  - 첫 번째 글자부터 끝까지 확인하면서 정답을 구한다.  코드 구현 : import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public static void main(String[] args) throws IOException { BufferedReader br ..

문제:https://www.acmicpc.net/problem/11052  접근 :   - 카드를 최댓값으로 N개 구매하기 위해서는 1 부터 N까지 구매 최대값을 알고 있어야한다.  - 카드 1개를 살때 최대값 (dp[1])은, card[1]이 최대값이다.  - 카드 2개를 살때 최대값 (dp[2])은 , card[1]을 2번 구매하는 값과 card[2] 중 더 큰 값이다.  - dp[3] 은, dp[1] + dp[2] 과 card[3] 중 더 큰 값이다.  - dp[4] = dp[1] + dp[3] , dp[2] + dp[2], num[4] 중 가장 큰 값이다.  - dp[5] = max { (dp[1] + dp[4]), (dp[2] + dp[3]), (card[5]) }   - dp[n] = max{..

문제:https://www.acmicpc.net/problem/3055  접근 :   - 물을 퍼뜨린다. 만약 돌이 있거나 동굴인 경우에는 지나가지 못한다.  - 두더지를 다음 경로로 이동시킨다. 만약 돌이 있거나 물이 있는 경우 지나가지 못한다.  - 만약 두더지가 동굴로 들어간다면, 동굴까지 걸린 시간을 출력한다.  - 만약 두더지가 동굴로 들어가지 못한다면, KAKTUS를 출력한다.   코드구현 : import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { private static boolean[][] waters; ..

문제:https://www.acmicpc.net/problem/14713  접근 :   - 앵무새의 말을 개별적으로 모은다.  - L 의 단어를 하나씩 비교하여 앵무새들이 할 말과 비교하여 없는 단어일 경우 Impossible을 반환한다.  - 만약 있다면, 그 앵무새의 다음 할 말로 포인터를 옮긴다.  - 모든 단어가 끝난 후에 앵무새의 말이 남아 있는지 확인한다.    코드구현 : import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { public static void main(String[] args) throws IOE..

문제:https://www.acmicpc.net/problem/3190  접근 :   - 1,1 에서 오른쪽으로 진행한다.  - 만약 사과가 있다면 몸의 길이(queue)를 늘린다.  - n초 뒤에 command(회전)이 있다면 command대로 머리를 돌린다.  - 만약 진행 중 벽을 만나거나, 자신의 몸에 부딛히면 종료하고 시간을 출력한다.    코드구현 :import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Objects;import java.util.Queue;public class Main { public..