목록Study/Problem Solving (163)
전공공부
설명 간단히 피보나치 수를 구현하고 이를 문제에서 주어진 조건에 따라서 모듈러 연산을 진행한다. 코드 package BOJ.Dynamic_Programming; import java.util.Scanner; public class BOJ_15624 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int [] dp = new int[N + 1]; if(N > 2) { dp[0] = 0; dp[1] = 1; dp[2] = 1; for (int i = 2; i
설명 DP로 풀면 되는 아주 쉬운 문제입니다. 연속된 부분 수열의 합을 구해서 최대한 큰 크기의 부분 수열의 합을 구하면 됩니다. 따라서, 지속적으로 연속된 부분 수열의 최대한의 합을 구하면 됩니다. 어떤 법칙이 있는 것이 아니라 예제를 보고 파악을 해보시는게 빠른 해답을 위한 길 입니다. 1 5 -2 1 2 3 -5 위와 같이 입력이 온다면 첫 번째 케이스를 빼고 [1] ~ [3] 까지의 부분 수열을 가져와서 합하면 되기 때문에 DP 반복문을 N 번 까지 체크 할 때 현재의 Max 연속된 부분 수열의 합을 지속적으로 구한다는 생각하면 됩니다. 코드 package BOJ.Dynamic_Programming; import java.util.Scanner; public class BOJ_10211 { pub..
설명 기본 DP문제로 워밍업 용으로 좋은 문제 인 것 같습니다. 문제에서 주어진 파스칼의 삼각형 공식을 사용했으며 (오른쪽 위 왼쪽 위를 더하면 아래의 조합 경우의 수가 나옴) 이때, 문제에서 주어진 삼각형의 경우의 수만큼 더했습니다. 코드 package BOJ.Dynamic_Programming; import java.io.BufferedReader; import java.io.InputStreamReader; public class BOJ_15489 { public static void main(String[] args) throws Exception{ BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String[] ..
설명 푸는데 걸린 시간은 매우 짧았지만 고민을 하면서 이 코드가 맞을지 확신을 가지지 못한채로 풀이를 진행했던 문제입니다. DP가 아직 익숙치 않으니 점화식을 짜는 것이 어색합니다. 빅 점프를 한 번만 할 수 있으므로 모든 경우에서 빅점프를 할 수 있는 경우를 열어 두고 빅 점프 이후에 다시 DP를 초기화하면서 점프에 대한 초기화를 진행하였습니다. N이 20이라 가능 한 경우이지 이렇게 매번 초기화 하는 방법 보다 index 값을 넘겨줘서 해당 index 이후로 부터만 보면 된다는 최적화식을 세울 수 도 있을 것이고 다른 좋은 방법이 있을겁니다. 코드 package BOJ.Dynamic_Programming; import java.io.BufferedReader; import java.io.IOExcep..
설명 계단 오르기 문제와 유사하다고 생각이 들었고 정말로 비슷하게 점화식을 수행하였습니다. 다만, Case가 연속된 3 Case를 구현하여야 하기 때문에 이전의 한 계단, 두 계단만 고려하던 연속적인 부분을 3케이스로 나누어서 선택하였습니다. 하나는 모두 3개를 선택하는 경우, 이전의 연속된 2개만 선택하는 경우, 현재 케이스를 스킵합니다. 헷갈릴 수 있는 부분이 제가 wine 배열은 N 개로 짜서 코드를 볼 때 인덱스 위치가 다르다는걸 감안해주셔야 합니다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * 계단 오르기 문제와 비슷하여 접근이 쉬웠습니다. */ p..
설명 아래 또는 오른쪽로만 움직일 수 있는 경우로 고정 되어 있습니다. 따라서, 점화식을 2차원 배열로 만들기 쉬운데요. dp를 해당 케이스로 가는 경우의 수로 고려하고 문제를 풀이를 시도하면 쉽게 세울 수 있는 DP 문제이나 처음에 점화식을 생각해내는 것이 역시 어렵습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ_1890 { public static void main(String[] args) throws IOException { BufferedReader in = new Buffe..
설명 조합의 경우의 수를 출력하기 위해서 N!/(N-M!)*M! 을 구현하였으며 100C5와 같이 long의 타입 길이를 침범하는 케이스가 존재하여 BigInteger를 이용하여 풀었습니다. 코드 package BOJ.Dynamic_Programming; import java.math.BigInteger; import java.util.Scanner; public class BOJ_2407 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); BigInteger sum = new BigInteger("1"); BigInteger div =..