오딩이

문제 : https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 🔎 Solve 다이나믹 프로그래밍(DP)을 이용하여 풀었습니다. 해당 문제를 표를 만들어서 생각해보면 점화식을 쉽게 만들어낼 수 있습니다. 문제에서 예제 입력 2번과 같이 N=6, K=4일 때를 예로 들어보겠습니다. 2차원 int형 배열을 만들어서 행에는 K (1~4)를, 열에는 N (0~ 6)을 나타내는 배열을 만들어줍니다. dp 0 1 2 3 4 5 6 1 2 3 4 해당 dp.배열을 K개의 숫자로 N을 만들 수 있는 경우의 수를 채워줍니다. 이때, K가 1개일 때는 각 숫자 자신만이 가능하니 1로 채워줍니다...

출처 : https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 🔍 Solve dp배열을 사용해서 풀었습니다. 처음엔 점화식이 너무 안 보여서 공책에 합이 1부터 10까지 나올 수 있는 모든 경우의 수를 적어보았습니다. dp의 기본적인 문제인 페인트칠하기와 규칙이 비슷해 보이는데 어떻게 풀 수 있을까 고민하다가 동전의 종류에따라 개수를 따로 세어주니 규칙을 찾을 수 있었습니다. 예제와 같이 동전의 종류가 1, 2, 5가 있습니다. 이 동전의 종류들을 담..

출처 : https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 🔍 Solve 다이나믹 프로그래밍으로 풀기 전, 완전 탐색으로 풀었을 때 시간 초과가 났던 문제입니다. 완전 탐색으로 풀었을 때 우선순위가 큰 것부터 선택하고 인접한 곳들을 지우는 방법으로 풀었습니다. isSelect배열을 선언하여 지워지는 곳은 1로, 선택된 곳은 2로 저장하였고, isSelect배열이 0이 아닌 수로 꽉 차면 break를 해주었습니다. 해당 방법은 테스트 케..

출처 : https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 🔍 Solve 완전 탐색으로 문자열 1과 문자열 2를 비교하는 방법을 생각했었는데, 카테고리가 dp인 만큼 시간 초과가 났습니다. dp배열에서 i=0, j=0일 때 i-1, j-1을 비교해야하기 때문에 dp배열의 크기는 (문자열 1의 길이+1) * (문자열 2의 길이+1)로 설정하였습니다. 문자열의 문자들을 비교하면서 문자가 같지 않을 땐 dp..