본문 바로가기

DP

 (11)
백준 15486 이진수 덧셈(파이썬) 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문제임을 알 수 있다. 나는 특정일에 얻을 수 있는 최대 이익을 구하는데 집중을 하였다. 먼저 특정일에 주어진 일을 기간안에 완수할수 있는지 없는지를 확인하여야 한다. 그렇기에 특정 일에 주어진 일을 마무리 할 수 있는 날을 구한다. fin_date = idx + T[idx] - 1 이후 ..
[백준] 9905 1, 2, 3 더하기 (JAVA) https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 위의 문제는 기본적인 dp문제이다. 우선 접근법은 간단하다. 우리는 어떠한 수 x가 들어온다고 하였을경우 x-1, x-2, x-3을 한다. 그 이후 각각의 수가 만약 이전에 계산하여 구했던 적이 있다면 그대로 dp배열에 있는 값을 반환해준다. 예를 들어 4를 x라고 하였을 경우 우리는 3 + 1, 2 + 2, 1 +3을 하여 경우의 수를 구하게 된다. 이때 각각의 연산값을 자세히 보면 3 + 1의 경우는 1, 2, 3만으로 3을 만들었는 경우에서 1을 각각 더하면 4가 되기에 우리는 dp[..
[백준] 1003 피보나치 함수 (JAVA) 풀이 이 문제는 dp를 이용한 피보나치 수열문제의 연장선이다. 문제에서는 0과 1이 출력하는 수 구하라고 하였는데 이는 곧 dp로 치환하여 풀면 다음과 같다. f_0(n) --> n일때 0의 출력수 f_1(n) --> n일때 1의 출력수 라고 가정을 한다면 이는 f_0(2) = f_0(1) +f_0(0), f_0(3) = f_0(2) + f_0(1) 과 같다. 그러므로 기존에 하던 dp그대로 하면된다. 하지만 여기서 주의해야할 점은 0과1 을 동시에 처리해줘야하는것이다. (아니면 시간초과가 난다... 자바....ㅜㅜ) 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import ja..
[백준] 2156 포도주 시식 (JAVA) https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이 이 문제는 계단오르기와 비슷한 유형의 문제이다. 우선 이전 포스팅에서도 말했듯이 현재 위치에서의 연속된 수를 구해서 풀이를 하는것이 아닌 경우를 나눠서 진행해야한다. 그러나 계단오르기와 다른점이 있다면 마지막 포도주는 선택을 안해도 된다는 것이다. 여기서 나는 조금 헤매었는데 결국은 dp중 최대값을 계속해서 선택을 하면 된다는 것이다. dp[x] = Math.max(Math.max(find(x..
[백준] 2579 계단 오르기 (JAVA) https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 나는 DP에 자신있다고 생각했는데 오만이였다. 나는 문제에 접글할때 재귀가 아닌 반복문으로만 생각을 하였고 이는 나를 오답으로 이끌었다. 사실 약 5달전에 풀어보았던 문제지만 다시 공부를 하며 풀어보았다. 그러나 생각대로 풀리지는 않았다. 조금더 공부에 신경을 써야 할것 같다. 알고리즘에 대하여 알아보기전 풀이에 도움을 받은 블로그에 대해서 링크를 남기겠다. https://st-lab.tistory.co..
[백준] 1932 정수 삼각형 (JAVA) https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 이 문제는 전형적인 DP로 DP를 조금 풀어보았더라면 쉽게 해결할수있는 문제이다. 알고리즘의 개요는 이러하다. 위에서부터 내려오는 방식과 밑에서부터 올라가는 방식이 있는데 나는 밑에서부터 올라가는 방식을 사용해서 문제를 해결했다. 우선 DP라는 2차원 배열과 ary이라는 2차원배열을 생성후 입력값을 ary에 저장한다. 그러고 난뒤 가장 ary의 가장 아랫부분을 dp에 저장하고 그 다음에는 다음과 같은 식을 수행한다 dp[i][j] = ary[i][j] + Math..
[백준] 1149 RGB거리 (JAVA) 풀이 이 문제는 정석적인 DP라고 볼수있겠다. 심지어 색도 3개이고 집의 개수도 적어서 시간 걱정 역시 안해도 된다. 문제에서 조건을 까다롭게 주었는게 결국은 인접한 집들끼리는 색이 겹처서는 안된다는 말이다. 알고리즘의 개요는 입력 받아 저장하는 2차원 int형 배열인 street와 dp를 만들면된다. 그러고 나서 dp의 첫번째 줄은 초기화를 해주고 그 다음은 겹치지 않는 색들끼리(dp) 비교해서 그 중 작은 값과 현재집의 특정색상과 더해서 저장 DP를 끝까지 수행해주면 dp[N-1]중에서 가장작은값을 출력. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.ut..
[백준] 2565 전깃줄 (JAVA) 풀이 이 문제는 가만히 생각하다 보니 복잡하지만 풀이가 보였다. 풀이 방법은 일단 문제에서 주어진 입력값을 전부 받고 그다음 가장 많이 겹치는 순으로 선을 제거해 겹쳐저있는 선들의 수를 계산 해나갔다. 그러나 이 방식으로 하면 시간도 오래걸리고 결론적으로 문제에서 틀렸다고 나오기도 하였다. (배열범위를 벗어났다고 나오지만...) 그래서 구글링을 하였고 역시 내가 생각한 풀이 방법보다 훨씬 깔끔했다. 나는 처음에는 문제에서 하라는대로 전선을 전부 이은후 하나씩 제거 해나갔는데 다른 사람들의 코드는 전부 연결한후 LIS방식으로 지우는 것이 아닌 최대 몇개까지 이을수있는것인가.를 구하고 전체에서 방금 구한수를 빼서 정답을 도출했다. 즉 전체집합에서 여집합을 빼서 구했다. 앞으로는 조금 유연하게 보도록 노력해야..
[백준]1937 욕심쟁이 판다 (JAVA) 풀이 이 문제를 처음보고는 할수있을듯 싶어 고민하였다. 조금 생각하다 내린 나의 결론은 이 문제는 DFS와 Dp를 이용해서 푸는 문제일 것이다. 그도 그럴것이 그래프 탐색과 유사하며 동일한 루트를 여러번 갈수도 있기에 시간을 줄이면 좋으므로 Dp또한 같이 적용시켜야 할것 같았다. 알고리즘의 전체적인 개요는 우선 대나무의 양이 저장되어있는 2차원 배열을 만든다. 그러고 나서 DFS를 적용할것이므로 visite2차원 배열을 만들어준다. 그리고 나서 마지막으로 DP를 2차원배열로 선언하는데 이때 나느 선언할때 값들을 1로 전부 초기화했다. 왜냐면 만약 상하좌우의 좌표의 대나무의 양이(막혀있지 않다고 가정하였을때) 현재 위치에 존재하는 대나무의 양보다 적으면 아무데도 이동할수는 없지만 그래도 적어도 현재 위치한..
[백준]11055 가장 큰 증가 부분 수열 (java) 풀이 이 문제는 전형적인 LIS문제중 하나이다. 문제는 크게 어려울것이 없이 기준값이 정해지면 인덱스의 처음부터 마지막까지 돌아가면서 만약 증가하는 부분수열을 만족한다면 DP에 저장하면 된다. 그렇게 기준값을 끝까지 돌리고 난후 DP에 저장되어있는 수들중 가장큰수를 출력하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(ne..

티스토리툴바