728x90 다이나믹 프로그래밍35 [JAVA]백준 2073번: 수도배관공사 www.acmicpc.net/problem/2073 2073번: 수도배관공사 아기염소들이 언덕에서 풀을 뜯고 놀다 보면 항상 도중에 목이 마르곤 했다. 그들은 불편함을 참지 못하고 수도관을 설치하여 거리 D(7 2021. 3. 6. [JAVA]백준 2758번: 로또 www.acmicpc.net/problem/2758 2758번: 로또 선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다. 이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는 www.acmicpc.net 1. 문제 설명 선영이가 매주 로또를 산다. 로또는 1부터 m까지의 숫자 중에서 n개의 수를 고르는 것이다. 수를 고를 때, 이전에 고른 수보다 적어도 2배가 되도록 고른다. n과 m이 주어졌을 때 선영이가 구매하는 로또의 개수를 구하는 문제. 2. 풀이 다이내믹 프로그래밍을 이용하여 풀 수 있다. dp [X][Y]= X번째 수를 고를 때 1부터 Y까지의 숫자 중에서 선택하는 경우의 수 = dp [X-1][Y/2]+dp.. 2021. 3. 5. [JAVA]백준 2631번: 줄세우기 www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 1. 문제 설명 1번부터 N번까지의 학생들이 순서대로 있지 않을 때 번호 순서대로 만들기 위해서 학생들을 이동시키는 최소 이동 개수 구하는 문제이다. 2. 풀이 LIS 알고리즘을 이용하여 풀 수 있다. 이미 순서대로 있는 아이들은 옮길 필요가 없고 순서대로 있지 않은 아이들만 옮기면 되기 때문에 LIS 알고리즘을 이용하여 최장 증가 부분 수열의 길이를 구하고 총 학생 수에서 수열의 길이를 빼면 된다. LIS 알고리즘은.. 2021. 3. 4. [JAVA]백준 2624번: 동전 바꿔주기 www.acmicpc.net/problem/2624 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 www.acmicpc.net 1. 문제 설명 지폐의 금액 T와 동전의 가짓수 K, 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 지폐를 동전으로 교환하는 방법의 가지 수를 구하는 문제이다. 2. 풀이 dp[x]= 현재 금액이 x일 때 동전으로 교환하는 방법의 가지 수 pi 금액의 가지수가 중복으로 포함되지 않도록 dp [x]에 대해 아직 pi 금액을 이용한 가짓수가 포함되지 않은 dp [x-ni*pi]의 값을 더했다... 2021. 3. 3. 이전 1 2 3 4 5 6 ··· 9 다음 728x90
