본문 바로가기
반응형

dynamic programming31

백준 4097 수익 Kotlin (dp) 문제 출처 : https://www.acmicpc.net/problem/4097 4097번: 수익 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N이 주어져 있다. (1 ≤ N ≤ 250,000) 둘째 줄부터 N개의 줄에는 매일 매일의 수익 P가 주어진다. (-10,000 ≤ P ≤ 10 www.acmicpc.net 문제 연종이는 창업했다. 오늘은 창업한지 N일이 되었고, 매일 매일 수익을 적어놓았다. 어느 날 연종이는 가장 많이 돈을 번 구간이 언제인지 궁금해졌다. 오늘이 창업한지 6일 되었고, 수익이 다음과 같다고 하자. 1일: -3 2일: 4 3일: 9 4일: -2 5일: -5 6일: 8 이때, 가장 많은 돈을 번 구간은 2~6까지이고 총 수입은 14이다. 입력 .. 2022. 8. 17.
백준 2294 동전 2 Kotlin (dp) 문제 출처 : https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 문제 n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000.. 2022. 8. 4.
백준 2293 동전 1 Kotlin (dp) 문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다. 알고리즘 분류 다이나믹 프로그래밍 풀이 dp 문제이다. dp[i] = i원을 만드는 경우의 수 예제에서 1,2,5라는 동전이 주어진다. 가치가 2인 동전으로 i원을.. 2022. 8. 1.
백준 14238 출근 기록 Kotlin (dp) 문제 출처 : https://www.acmicpc.net/problem/14238 14238번: 출근 기록 스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다. 이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의 www.acmicpc.net 문제 스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다. 이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의 출근 기록이 "AAC"라는 것은 처음 이틀은 A가 출근했고, 셋째 날엔 C만 출근했다는 뜻이다. A는 매일 매일 출근할 수 있다. B는 출근한 다음날은 반드시 쉬어.. 2022. 7. 21.
백준 12969 ABC Kotlin (dp) 문제 출처 : https://www.acmicpc.net/problem/12969 12969번: ABC 첫째 줄에 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. 만약, 그러한 S가 존재하지 않는 경우에는 -1을 출력한다. www.acmicpc.net 문제 정수 N과 K가 주어졌을 때, 다음 두 조건을 만족하는 문자열 S를 찾는 프로그램을 작성하시오. 문자열 S의 길이는 N이고, 'A', 'B', 'C'로 이루어져 있다. 문자열 S에는 0 ≤ i < j < N 이면서 S[i] < S[j]를 만족하는 (i, j) 쌍이 K개가 있다. 입력 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 30, 0 ≤ K ≤ N(N-1)/2) 출력 첫째 줄에 문제의 조건을 만족하.. 2022. 7. 18.
백준 1301 비즈 공예 Kotlin (dp) 문제 출처 : https://www.acmicpc.net/problem/1301 1301번: 비즈 공예 첫째 줄에 다솜이가 가지고 있는 구슬의 종류 N이 주어진다. N은 3보다 크거나 같고, 5보다 작거나 같다. 둘째 줄부터 N개의 줄에 각각의 구슬이 총 몇 개 있는 지주어진다. 첫째 줄에는 1번 구슬, www.acmicpc.net 문제 다솜이는 자신의 목걸이를 구슬을 이용해서 만들려고 한다. 다솜이는 구슬을 N종류 가지고 있다. 서로 다른 종류의 구슬은 색이 다르다. 다솜이는 구슬을 실에 껴서 목걸이를 만들려고 한다. 무작정 껴도 상관없겠지만, 워낙 미적감각이 뛰어난 다솜이는 임의의 연속된 3개의 구슬의 색을 모두 다르게 하려고 한다. 예를 들어, 다솜이가 1번 구슬을 2개, 2번 구슬을 1개, 3번 .. 2022. 7. 16.
백준 18427 함께 블록 쌓기 Kotlin (dp) 문제 출처 : https://www.acmicpc.net/problem/18427 18427번: 함께 블록 쌓기 첫째 줄에 자연수 N, M, H가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10, 1 ≤ H ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 각 학생이 가진 블록들의 높이가 공백을 기준으로 구 www.acmicpc.net 문제 1번부터 N번까지의 학생들은 각각 블록들을 가지고 있다. 학생마다 최대 M개의 블록을 가지고 있을 수 있으며, 한 명의 학생이 가지고 있는 모든 블록들의 높이는 서로 다르다. 이 때 1번부터 N번까지의 학생들이 가진 블록을 차례대로 사용하여 바닥에서부터 쌓아올려 하나의 탑을 만들고자 한다. 단, 어떤 학생의 블록은 사용하지 않아도 되며 한.. 2022. 7. 15.
백준 2011 암호코드 Kotlin (dp) 문제 출처 : https://www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 문제 상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다. 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야. 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어. 상근: 그렇네. 25114를.. 2022. 7. 13.
프로그래머스 멀리 뛰기 Kotlin (dp) 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 문제 설명 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2칸) 의 5가지 방법으로 맨 끝 칸에 도달.. 2022. 4. 23.
반응형

티스토리툴바