본문 바로가기

Problem Solving/DP

BOJ 2342 - dance dance revolution 문제 링크https://www.acmicpc.net/problem/2342 문제 해결 1. dp[l][r][stage] : 현재 stage에서 왼발이 l, 오른발이 r에 위치할 때 사용한 최소의 힘 주의할 점 || 생각해볼 점 1. 그리디라고 생각할 수 있지만 항상 현재 해가 최적이 될 수 없다. 아래는 현재 상황에서 가장 적은 힘을 사용해서 움직였을 때의 cost. 아래는 현재 상황에서 가장 적은 힘을 사용해서 움직였을 때의 cost. 그리디로 해결할 수 없다. 그러므로 DP를 이용해서 해결해야한다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기
BOJ 1495 - 기타리스트 문제 링크(Link)https://www.acmicpc.net/problem/1495 문제 해결(Solution) 1. dp[i][j] : i번 곡에서 j만큼의 볼륨을 가질 수 있는 지에 대한 여부. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 재귀함수 안에서 볼륨 j가 0보다 작은 지 또는 M보다 큰지 제일 먼저 확인해줘야 한다. 2. 만약 볼륨 값이 범위를 넘어가게 되면 의미없는 수를 반환해야한다. 그렇지 않으면 그 값이 계속해서 다른 재귀함수에 사용된다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기
BOJ 1038 - 감소하는 수 문제 링크https://www.acmicpc.net/problem/1038 문제 해결 1. 전체 감소하는 수는 1023개밖에 안되기에 전체 탐색이 가능하다 2. recursive하게 돌아볼 수 있다. 주의할 점 || 생각해볼 점 1. 9,876,543,210 은 int 범위를 넘어가기에 long long으로 선언해야한다. 2. 0번째 감소하는 수가 0이므로 set.size()가 N+1 같거나 커야한다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기
BOJ 14585 - 사수빈탕 문제 링크https://www.acmicpc.net/problem/14585 문제 해결 1. (0, 0) 에서부터 x 좌표가 증가하는 방향과 y 좌표가 증가하는 방향으로만 이동한다. → Dynamic Programming으로 해결할 수 있음을 알 수 있는 부분. 주의할 점 || 생각해볼 점 1. M의 값이 1,000,000이고 N의 값이 300이면 M*N = 3억이 될 수 있으므로 (int형 범위를 초과할 수 있으므로) 자료형은 long long을 선택한다. 2. 매 시간마다 1씩 줄어드는 것을 따로 구현할 필요가 없이 가로와 세로의 값을 최초 사탕의 값에서 빼주면 된다. ( a[x][y] - (x+y) ) 3. 처음 문제를 봤을 때, BFS(넓이 우선 탐색)를 이용해서 문제를 해결하려 했다. 그러나 문.. 더보기
BOJ 12758 - 토쟁이의 등굣길 문제 링크https://www.acmicpc.net/problem/12785 문제 해결 1. DP[i][j] = (1, 1)에서 (i, j)까지 가는 경우의 수 2. DP[i][j] = DP[i-1][j] + DP[i][j-1] 3. a : (1, 1)부터 토스트 집의 좌표 (x, y)까지의 경우의 수 b : (x, y)부터 학교까지의 경우의 수(M, N)까지의 경우의 수 → (x, y)를 (1, 1)로, (M, N)을 (M-x+1, N-y+1)로 생각하자. a*b가 답이된다. 주의할 점 || 생각해볼 점 1. 1,000,007로 계산할 때마다 나누어 줘야한다. 2. a와 b 모두 1,000,007이 넘지 않는다고 해도 곱하는 과정에서 넘어갈 수 있기에 long long 자료형을 사용한다. 참고 - ※ .. 더보기
BOJ 5557 - 1학년 문제 링크https://www.acmicpc.net/problem/5557 문제 해결 1. DP[i][j] = 첫 번째부터 i 번째까지의 합 또는 차가 j 인 경우의 개수 주의할 점 || 생각해볼 점 1. 처음부터 i 번까지의 합이 0 이상 20 이하임을 인지한다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기
BOJ 1695 - 팰린드롬 만들기 문제 링크https://www.acmicpc.net/problem/1695 문제 해결 1. dp[i][j] = 인덱스 i 부터 j 까지의 끼워넣는 수의 최소값. 주의할 점 || 생각해볼 점 1. i가 j를 넘어갈 수 있음을 고려해줘야한다. 참고 ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기
BOJ 11066 - 파일 합치기 문제 링크https://www.acmicpc.net/problem/11066 문제 해결 1. dp[i][j] = i번 장에서 j번 장까지 합치는 데 드는 최소값. 주의할 점 || 생각해볼 점 1. 부분 합으로 미리 구간의 합을 구해놓으면 시간을 절약할 수 있다. 참고 - 부분 합 : http://terms.naver.com/entry.nhn?docId=849492&cid=50376&categoryId=50376 ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기
BOJ 1254 - 팰린드롬 만들기 문제 링크https://www.acmicpc.net/problem/1254 문제 해결 1. 팰린드롬 확인하는 최대 횟수 : 1,000 만들 수 있는 문자열의 최대 길이 : 1,999 → 2,000,000 이하 이므로 Brute force 가능 ( 왜 DP로 분류되는 이유를 모르겠다...) 주의할 점 || 생각해볼 점 1. 0개 이상 붙이는 것이므로, 이미 팰린드롬이면 그냥 길이를 출력해야한다. 참고 - 팰린드롬 (회문) : https://ko.wikipedia.org/wiki/%ED%9A%8C%EB%AC%B8 - brute force : https://namu.wiki/w/%EB%B8%8C%EB%A3%A8%ED%8A%B8%20%ED%8F%AC%EC%8A%A4 ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기
BOJ 3943 - 헤일스톤 수열 문제 링크https://www.acmicpc.net/problem/3943 문제 해결 1. 문제 그대로 짝수와 홀수일 경우를 나눠서 재귀 형식으로 구현 2. DP[i] = i로 시작하는 헤일스톤 수열이 가질 수 있는 가장 큰 수 주의할 점 || 생각해볼 점 1. N의 범위가 100,000까지라고 해도 계산 시 100,000을 넘어갈 수 있다. ex) 99,999같은 경우 2. 100,000이 넘어가는 경우는 배열에 저장하지 않고 계산한다. 참고 - 콜라츠 추측 (우박 수열 or 헤일스톤 수열) : https://namu.wiki/w/%EC%BD%9C%EB%9D%BC%EC%B8%A0%20%EC%B6%94%EC%B8%A1 ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기

티스토리툴바