본문 바로가기

dp8

[백준 1943번] 동전 분배 난이도: 골드 III 문제 링크: https://www.acmicpc.net/problem/1943 1943번: 동전 분배 세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1≤N≤100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원장선 www.acmicpc.net DP를 통해 접근할 수 있는 문제입니다. 그리디로 왜 안 되는지는... 잘 모르겠네요 ㅠ 모든 동전의 값의 합을 먼저 구하고, 이것이 홀수라면 반으로 나눌 수 없으므로 0을 출력하고 넘어갑니다. 짝수라면, 총 값의 반을 최대 기준으로, 만들 수 있다면 해당 테이블에 1을 기록하며 진행합니다. 이전 인덱스의 값을 참조하여 진행하기 때문에 탑-다운 방식으로.. 2021. 9. 30.
[백준 1823번] 수확 난이도: 골드 III 문제 링크: https://www.acmicpc.net/problem/1823 1823번: 수확 첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다. www.acmicpc.net 벼가 한 줄로 쭉 세워져 있고, 벼의 가치는 각각 입력으로 들어옵니다. 벼를 나중에 수확할수록 이익을 더 얻기 때문에, 끝까지 가 봐야 알 수 있으므로 그리디 방식으로는 해결할 수 없습니다. 이 문제의 경우, DP를 이용하여 접근할 수 있습니다. 보통 DP 문제의 경우 맨 마지막 값이 정답이 되는데, 이 문제의 경우 배열의 앞과 뒤를 좁혀 가며 탐색을 하므로, 중간의 어느 지점이 맨 마지막에 탐색하.. 2021. 9. 29.
[백준 1727번 문제] 커플 만들기 난이도: 골드 III 문제 링크: https://www.acmicpc.net/problem/1727 1727번: 커플 만들기 첫째 줄에 n, m(1≤n, m≤1,000)이 주어진다. 다음 줄에는 n명의 남자들의 성격이 주어진다. 그 다음 줄에는 m명의 여자들의 성격이 주어진다. 성격은 1,000,000이하의 자연수이다. www.acmicpc.net 문제를 이해하는데 다소 어려움이 있었는데, 문제를 요약하면 다음과 같습니다. 커플의 수는 최대여야 한다. 즉 남자의 수 n, 여자의 수 m이 있을 때, 커플의 수 = min(n, m)이 된다. 커플을 만들었을 때, 성격의 차이를 각각 구하고, 이 값을 누적한다. 누적한 값이 최소가 되도록 하라. 다이나믹 프로그래밍 문제입니다. 입력을 두 배열 men, wome.. 2021. 9. 26.
[백준 2042번] 구간 합 구하기 난이도: 골드 I 문제 링크: https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 이 문제는 세그먼트 트리라는 알고리즘을 알아야 풀 수 있는 문제입니다. 기본적인 설명은 여기를 참고해 주세요. 세그먼트 트리의 기본적인 문제입니다. 한 가지 유의할 점이 있다면, 값을 수정할 때입니다. b의 값을 c만큼 수정하는 것이 아니라, b의 값을 c로 수정하는 것입니다. 따라서 차이값 differenc.. 2021. 9. 25.
세그먼트 트리 다음과 같은 문제를 생각해 봅시다. 배열 arr에는 수많은 int형 정수가 들어 있다. arr의 크기 n은 최대 10만이며, 각 정수는 1000 이하의 크기를 가진다. 배열이므로, 당연히 arr의 모든 원소는 인덱스가 정해져 있다. 인덱스는 0부터 시작한다. 총 m줄에 걸쳐 구간이 주어질 때, 주어진 구간합을 출력하는 코드를 작성하시오. (n 2021. 9. 25.
[백준 3687번] 성냥개비 난이도: 골드 II 문제 링크: https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 제가 느끼기에 이 문제는 DP와 그리디를 이용하는 부분으로 나뉩니다. 그리디를 이용하는 부분은 최댓값을 구하는 부분으로, 상대적으로 더 쉽습니다. 성냥개비가 짝수개 있을 때는, 모두 1을 만들면 됩니다 (자릿수를 크게 함). 1을 만드는 데 성냥개비가 2개 소모되므로, 총 (성냥개비 개수 / 2)개의 1을 출력합니다. 성냥개비가 홀수개 있을 때는, 맨 앞자리에 7을 출력하.. 2021. 9. 9.

티스토리툴바