본문 바로가기
728x90

분류 전체보기129

[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.
[JAVA]백준 15724번: 주지수 www.acmicpc.net/problem/15724 15724번: 주지수 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 www.acmicpc.net 1. 문제 설명 네모 왕국의 영토 1*1 단위 구역이 주어지고 단위 구역마다 살고 있는 사람 수가 주어진다. X1, Y1, X2, Y2좌표가 주어질 때 주어진 직사각형 범위에 살고 있는 사람의 수를 구하여라. 2. 풀이 dp[x][y]= X1=1, Y1=1, X2=x, Y2=y 직사각형 범위에 살고 있는 사람의 수 = dp[x-1][y]+dp[x][y-1]+x,y 좌표에 살고 있는 사람 수 -dp [x-1][y-1].. 2021. 3. 2.
[JAVA]백준 1823번: 수확 www.acmicpc.net/problem/1823 1823번: 수확 첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다. www.acmicpc.net 1. 문제 설명 1*N 크기의 긴 밭에 심어진 벼를 수확하려고 한다. 벼는 양끝에 있는 벼만 수확을 할 수 있다. 수확을 하였을 때 얻을 수 있는 이익은 벼의 가치 v(i) * 벼를 수확한 순서 k의 합이다. 벼를 수확할 때 얻을 수 있는 최대 이익을 구하시오. 2. 풀이 dp로 Top down 방식과 Bottom Up 방식으로 풀 수 있다. 1) Top down (재귀) cut(start, end, num) = 현재 남은 벼가 start 인덱스.. 2021. 2. 26.
728x90

티스토리툴바