본문 바로가기

BackJoon/DP

 (6)
5557.1학년 https://www.acmicpc.net/problem/5557 5557번: 1학년 문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다. 상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. www.acmicpc.net 아 진짜 이문제 당연히 모든 경우 다해봐야하는거 아니야?? 라고 화내며 못풀었던문제. 정말 DP는 풀때마다 새롭고,,, 스킬이 늘긴느는지....
7579.앱 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활성화 되어 있는 앱 A1, ..., AN이 사용 중인 메모리의 바이트 수인 m1, ..., mN을 의미하며, 셋째 줄의 정수는 각 앱을 비활성화 했을 경우의 비용 c1, ..., cN을 의미한다 단, 1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000,000이며, 1 www.acmicpc.net 보자마자 평범한 배낭 문제가 생각났다. 똑같이 풀면된다. //dp 배열 int[][] b = new int[2][M+1]; for(int[] ..
12865.평범한 배낭 package dynamicProgramming; import java.util.Scanner; public class KnapSack { public static void main(String[] args) { Scanner scan= new Scanner(System.in); //물건갯수와 무게K int N = scan.nextInt(); int K = scan.nextInt(); //dp배열 int[][] c = new int[N+1][K+1]; //무게와 가치 int[] W = new int[N+1]; int[] V = new int[N+1]; W[0]=0; V[0]=0; for(int i=1;i
2156. 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 풀이1) 길이기 3이상이면 무조건 1-n번 중하나는 안마셔야한다는 점을 생각해 케이스를 나눴다. for(int i=0;i
2169. 로봇 조종하기 https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 문제는 익숙한 형태였다. 1.1에서 N,M으로 가면서 가치가 최대가 되도록하기 하지만 로봇을 왼쪽 오른쪽 아래쪽으로 이동할 수 있다는 조건 때문에 어려웠다.. 자바코드는 다음과 같다. //i,j 까지 최대 가치를 저장하는 배열 int[][] dp = new int[N][M]; //첫번째 줄은 그냥 왼쪽으로 가는게 최대 dp[0][0]=map[0][0]; for(int i=1;i
1904번. 01타일 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수 www.acmicpc.net 배운점 : DP문제는 케이스 체크를 잘 하자 뭔가 풀면서 피보나치 같았지만, 정확한 이유를 모르겠어서 풀지 못했던 문제이다. 피보나치 문..

티스토리툴바