본문 바로가기

동적계획법27

[백준/C,C++] 7579번: 앱 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 풀이 해당 문제에서 앱의 개수는 100개 이하이고, 확보해야하는 메모리는 10,000,000바이트 이하입니다. 100 x 10,000,000 는 10억으로 너무 크기 때문에, 비활성화 했을 경우의 최대 비용인 100을 사용해 DP 점화식을 짜야합니다. DP[i]를 i의 비용이 주어졌을때 확보할 수 있는 최대 메모리라고 가정해봅시다. 5 60 30 10 20 35 40 3 0 3 5 4 의 예제로 보겠습니.. 2021. 7. 5.
[백준/C,C++] 2293번: 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 생각보다 어려운 문제였습니다. 1, 2, 5원을 1번 이상 사용해 만들 수 있는 1~10원의 경우의 수는 아래 표와 같습니다. 0 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 1 1 누적 1 1 1 1 1 1 1 1 1 1 1 2 0 0 1 1 2 2 3 3 4 4 5 누적 1 1 2 2 3 3 4 4 5 5 6 5 0 0 0 0 0 1 1 2 2 3 4 누적 1 .. 2021. 7. 5.
[백준/C,C++] 2629번: 양팔저울 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 플이 티스토리 꾸준함님의 풀이를 참고하여 풀었습니다. 추를 구슬이 없는 쪽에 올릴지, 구슬이 있는 쪽에 올릴지, 아무 곳에도 올리지 않을지 3가지의 경우를 재귀 호출하며 풀 수 있는 문제입니다. 두번째 예제인 4 2 3 3 3 3 1 4 10 으로 예를 들어보겠습니다. 2, 3, 3, 3의 추 중에 두번째 추까지를 올린다고 해봅시다. 빨간색의 경우 추를 구슬이 없는 쪽에 올리는 경우, 흰색의 경우 .. 2021. 7. 5.
[백준/C,C++] 10942번: 팰린드롬? https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이 1, 2, 1, 3, 1, 2, 1로 예를 들어보겠습니다. S = 1, E = 7일 경우 1과 1이 같고 그 중간 범위인 2, 1, 3, 1, 2가 팰린드롬이면 팰린드롬입니다. S = 2, E = 6일 경우 2와 2가 같고 그 중간 범위인 1, 3, 1이 팰린드롬이면 팰린드롬입니다. S = 3, E = 5일 경우 1과 1이 같고 그 중간 범위인 3이 팰린드롬이면 팰린드롬입니다. 수가 하나일 경우 무조건 팰린드롬이므로 S = 1, .. 2021. 7. 5.

티스토리툴바