0m1n's Develog

문제 출처 : https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 DP로 해결하는 문제이다. 뒤에서부터 탐색하는 방식으로 해결하였으며 앞에서부터 탐색하는 방법도 있다. dp[i]를 i일부터 시작했을때의 최댓값 이라고 하였다. dp는 동적할당을 해주고 문제의 Ti와 Pi는 vector에 넣어주었다. ※ 1차원 배열 동적할당에서, new int[N]뒤에 ()을 붙이면 0으로 초기화 해준다. int *dp = new ..

문제 출처 : https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 DP 기초 문제이다. 10 이하의 정수를 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제이다. dp[i]를 i 를 1, 2, 3 으로 나타내는 방법의 수라고 하자. dp[1]은 1로만 나타낼 수 있으므로 1, dp[2]는 2, 1+1 이므로 2, dp[3]은 3, 2+1, 1+2, 1+1+1 이므로 4이다. ※ 2, 3의 경우도 점화식으로 나타낼 수 있는데, dp[2] = dp[1] + 1(2로 나타낼 수 있으므로) dp[3] = dp[1] + dp[2] + 1(3으..

문제 출처 : https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 풀이 DP로 해결하였던 문제이다. 동전의 종류가 주어지고 주어진 금액을 만드는 모든 경우의 수를 세는 문제이다. 점화식은 다음과 같다. for(int i = 0; i T; while (T--){ int dp[10000 + 1] = {0, }; int N; cin >> N; vector coin(N); in..

문제 출처 : https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 배낭 알고리즘이라고도 불리는 Knapsack 알고리즘의 대표 문제이다. 여러가지 케이스가 있을때 특정 조건을 만족하는 값, 조합 등을 구하는 문제들이며 대부분 DP로 해결할 수 있다. 이 문제 역시 DP로 해결 할 수 있는데 문제를 요약해보면, 각 물건의 무게(W)와 가치(V)가 주어지고, 배낭의 용량(K)이 주..

문제 출처 : https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 풀이 브루스포스로 해결하면 시간 초과가 발생한다. map을 이용해서 듣도 못한 사람을 저장하고, 보도 못한 사람을 해당 map에서 찾아 있는 경우 vector에 추가 해주었다. sort 함수를 사용해 사전순으로 출력하였다. (sort를 사용하려면 algorithm 헤더 파일을 선언해주어야 한다!) 이분탐색(binary_search)을 활용해 겹치는 사람을 찾는 방법도 있다. 아래 ..