냅색 알고리즘 문제의 정석n개의 물건,,k 무게까지 버티는 가방,, 최대 가치,, 0\. 입력 받기1\. dp 배열 정의하기dp\[i]\[j] = 물건 무게의 합이 j일때, 처음 i개의 아이템 중 담을 수 있는 최대 가치2\. 현재 물건을 담았을 때 vs 담지 않았을

문제 https://www.acmicpc.net/problem/14728 한 문제를 맞기 위해선 특정 시간 이상 공부를 해야할 때, 주어진 시간 안에 얻을 수 있는 최대 점수를 구하면 된다. 인덱스 에러때매 돌아버릴뻔 문제 풀이 입력 받기 과목을 공부할 때 소

https://www.acmicpc.net/problem/3067N가지의 동전 종류가 주어질 때, M원을 만들 수 있는 방법의 수를 구하면 된다.dp와 그리디 알고리즘을 비교할 때 자주 등장하는 전형적인 문제라고 한다.입력 받기want원을 만드는 방법의 수를

https://www.acmicpc.net/problem/7579M byte 이상의 메모리를 확보할 때, 소요되는 가장 적은 비용을 구하면 된다.쥔챠,,. 냅색은 풀어도 풀어도 적응이 안된다.내가 작성해놓은 코드를 보아도 매번 초면이다. 누구세요?입력 받기dp

https://www.acmicpc.net/problem/12015\[11053 가장 긴 증가하는 부분 수열] 이랑 동일한 풀이로 제출했다가 시간 초과가 났다. . . 🙂🙃🙂dynamic programming 중 특별케이스인 lis에 대해 알 수 있었던

문제 https://www.acmicpc.net/problem/9465 (i,j)에 위치한 스티커를 떼면, 상하좌우가 찢어진다. 🧩 스티커에 뗀 뒤 가장 큰 점수를 구하는 문제다. 문제 풀이 dp 배열을 확실하게 잡고 가면, 문제 풀기가 수월하다. 우선 2열까

https://www.acmicpc.net/problem/11052n개의 카드를 구매할 때, 가장 비싸게 구매할 수 있는 금액을 구하는 문제다.dp\[i] = 카드 i개를 구매할 때 가질 수 있는 금액의 최댓값우선 n이 3보다 작을 때 값을 정의해주었다.n이

https://www.acmicpc.net/problem/9461p(n)은 나선에 있는 정삼각형의 변의 길이다.그림을 그리면 쉽게 풀 수 있다.약간 지저분하지만,, 어떤 걸 더해야 다음 항을 구할 수 있는지 직관적으로 확인할 수 있다.

https://www.acmicpc.net/problem/2193n개의 자릿수에 대한 이친수 개수 구하기~2xn 타일링 문제와 동일하게 겹치는 경우의 수를 제외하고 세주면 된다.dp\[i] = i 자리의 이친수 개수1\. 첫번째 자리는 반드시 1로 시작한다.2

문제 https://www.acmicpc.net/problem/11727 문제 풀이 코드

https://www.acmicpc.net/problem/11053수열의 요소를 골라서 가장 긴 부분 수열을 만든 뒤, 그 수열의 길이를 출력하면 된다.dp\[i] = 수열의 i번째 요소까지 만들 수 있는 가장 긴 배열의 길이 ( i >= 1 )부분 수열의 값

https://www.acmicpc.net/problem/190401타일 분명히 어려웠는데..냅색 풀다가.. 이제 보니 선녀같다.점화식만 세우면 금방 풀 수 있다.d(n) = 타일 크기가 n일 때, 만들 수 있는 가짓수d(0) = 0 d(1) = 1 (1)d(

https://www.acmicpc.net/problem/4781냅색 기초 문제라고 해서 후딱 풀었다.냅색 알고리즘을 모르신다면,, 함 읽어보세요~! (🔗 링크)구매할 수 있는 금액이 정해져있을 때, 최대의 칼로리를 구하는 문제다.이전에 푼 냅색 문제와 동일

냅색 문제 냅다풀기

골라골라

https://www.acmicpc.net/problem/11055배열에서 특정 숫자들을 빼면 증가 수열이 된다.그 증가 수열들 중 가장 합이 큰 수열을 구하는 문제다.증가 부분 수열에 대해서 찾아보는데에 시간이 더 걸렸던 것 같다.나무위키 에 설명이 굉장히

https://www.acmicpc.net/problem/2156포도주를 최대한 많이 마시는 문제다. 부럽다🙃이때 3잔 연속으로 마실 수 없다는 점을 고려해야 한다.포도주의 양을 기록해줄 dist 리스트를 만들어주었다.disti에는 i번째 위치에 왔을 때,

https://www.acmicpc.net/problem/1149n개의 집들을 퐁당퐁당 다른 색으로 칠하는 문제이다.(n-1)과 (n) / (n)과 (n+1)은 색이 달라야한다.각 집마다 색을 칠하는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하면

https://www.acmicpc.net/problem/1010강 서쪽에 n개의 지점, 강 동쪽에 m개의 지점이 있을 때 n개의 다리를 지으려고 한다. (n <= m)중요한 것은 이때 다리가 겹치면 안된다는 것이다.dp 문제는 그림을 그려야 눈에 확 들

https://www.acmicpc.net/problem/1003재귀 형태의 피보나치 함수가 있을 때, fibo(n)에 대해서 fibo(0)과 fibo(1)이 몇번 호출되는지 구하는 문제다.문제를 처음 접했을 때 어떻게 접근해야 할지 감이 안잡혔다.그래서 직접