백준52 [12865번] 평범한 배낭 배낭(Knapsack) 문제 중 짐(item)을 쪼갤 수 없는 0-1 냅색 문제DP(동적계획법)의 대표적 문제 중 하나입력은 N(item의 개수), K(배낭의 최대 무게)와 각 item의 w(무게), v(가치)이다.입력을 바탕으로 배낭에 넣은 물건의 가치의 합이 최대가 되도록 한다.점화식을 세워보면 아래와 같이 나타낼 수 있다.DP( i, w ) = | max( DP( i, w ) , DP[ w - item[i].weight ] + item[i].value ] ) ( item[i].weight w )( i : 현 아이템 번호, w : 현 배낭의 무게 )여기서 w를 최대 K부터 1까지 줄여가면서 배낭을 채워나가고 현 아이템에 대해 기록이 끝났다면 다음 아이템으로 넘어가서 반복하도록 한다.예시로, 4 7 /.. 2020. 8. 4. [12100번] 2048(Easy) 12100번: 2048 (Easy) www.acmicpc.net 2048에서 여러 조건이 빠진 문제이다.위 아래 왼쪽 오른쪽으로 이동시킬 수 있고 이동시 같은 숫자의 블록을 만나면 서로 합쳐진다.블록이 합쳐지는 우선순위는 이동 방향쪽이 우선이다. 주의해야 할 조건은 1. 한 번의 이동에서 이미 합쳐진 블록은 다른 블록과 다시 합쳐질 수 없다.ex) 에서 위로 이동할 경우가 아니라 가 되어야 한다. 2. 최대 5번의 이동이 가능하다. 맵의 크기가 20 * 20으로 완전탐색으로 풀 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656.. 2020. 4. 21. [17136번] 색종이 붙이기 17136번: 색종이 붙이기 www.acmicpc.net 1*1, 2*2, 3*3, 4*4, 5*5 크기의 색종이가 각각 5장 씩 주어진다. 이 색종이들 만 이용해서 주어진 공간에 완벽하게 붙이면 된다. 조건1. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안된다.2. 겹쳐도 안 된다.3. 칸의 경계와 일치하게 붙여야 한다. 즉, 0이 적힌 칸에는 색종이가 있으면 안 된다. 맵의 크기가 10*10으로 작기 때문에 완전탐색으로 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777.. 2020. 4. 11. [17406번] 배열 돌리기4 17406번: 배열 돌리기 4 www.acmicpc.net 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 회전연산 이란, 아래 그림 처럼 배열을 회전시키는 연산이다. 주어진 회전 연산의 정보에 따라 회전한 배열 A의 값중 최소값을 출력하는 문제다. 구현력을 보는 문제인듯 하다. 1. 회전 연산의 순서를 정하고 (순열)2. 정해진 순서에 맞춰 회전 연산을 수행 (회전)3. 연산이 끝난 배열의 값을 구해서 최소값을 구한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676.. 2020. 4. 11. 이전 1 2 3 4 ··· 13 다음
