dp

[백준] 1562. 계단 수 - Python

[Gold I] https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 비트마스킹을 이용한 DP 문제. 기본적인 아이디어는 2차원 DP를 생각하면 쉽게 떠올릴 수 있는데, dp[N][i] 일 때, dp[N][i] = dp[N-1][i-1] + dp[N-1][i+1] 과 같은 점화식(i==0, i==9 예외) 으로 풀이할 수 있다. 다만 위의 경우는 0부터 9까지 숫자가 모두 등장하는 계단 수 라는 조건을 무시했을 때의 풀이법. 이 문제는 위 조건을 만족하는 수의 개수만을 구해야 하므로, 기존 풀이를 응용하여 풀이할 수 있다. 기존 2차원 배열이 아닌, 3차원 배열로 선..

[백준] 12026. BOJ 거리 - Python

[Silver I] https://www.acmicpc.net/problem/12026 12026번: BOJ 거리 스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다. www.acmicpc.net 풀이 간단한 DP 문제. 맨 마지막 (N번)에서부터 출발하여, 1번까지 필요한 에너지의 양의 최소를 기록하며 나아가면 된다. (dp[i] => (i+1)번부터 N번까지 이동하는 데에 사용하는 에너지의 최솟값) dp 배열을 생성하여, N번부터 1번까지 모두 순회하며, 현재 위치보다 더 앞쪽에 있는 가능한 위치로의 에너지 최솟값을 기록하자. 예를 들어, 아래와 같은 input이 들어왔다고 가정하자. 9 BOJBOJBOJ 우선 dp[8] = ..

[백준] 2780. 비밀번호 - Python

[Silver I] https://www.acmicpc.net/problem/2780 2780번: 비밀번호 각각의 Test case에 대해서 조건을 만족하는 비밀번호의 개수를 출력하라. 단, 수가 매우 커질 수 있으므로 비밀번호의 개수를 1,234,567으로 나눈 나머지를 출력하라. www.acmicpc.net 풀이 간단한 DP 문제. 비밀번호 길이가 i일 때, j라는 숫자에서 출발했을 때의 비밀번호 개수를 dp[i][j] 라 하자. 인접한 번호로만 갈 수 있으므로, dp[i][j] 는 인접한 숫자들의 dp[i-1][~] 들의 합으로 구할 수 있다. 점화식은 대충 표현하자면 아래와 같다. # dp[i][j] = dp[i-1][(인접한 숫자)] 들의 합 # ex) dp[3][2] = dp[2][1] + d..

[백준] 15846. 퇴사 2 - Python

[Gold V] 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 풀이 1 문제를 보니, Greedy는 아닌 것 같고.. DP로 접근해야겠다는 생각으로 문제를 읽기 시작. 첫 시도에는, 1차원 dp이고, 1일차 부터 Bottom-Up으로 채워나가는 식으로 접근하려고 시도했다. 예제 입력 1 은 아래와 같다. 1일2일3일4일5일6일7일 Ti3511242Pi102010201540200 이런 상황에서, 1일차부터 접근하면..

[백준] 2169. 로봇 조종하기 - C++

[Gold II] https://www.acmicpc.net/problem/2169 풀이 일반적인 Bottom-Up 형식으로 풀어낸 DP 문제. 아래, 오른쪽으로만 갈 수 있는 것이 아닌, 왼쪽으로도 갈 수 있기 때문에 이를 고려해줘야 했으나, "한 번 방문한 곳은 다시 방문하지 않는다" 라는 조건이 있기 때문에, 각 줄에서, 왼쪽부터 DP 배열을 갱신하고 (line 43~45), 또 오른쪽부터 다른 DP배열을 갱신한 후 (line 47~49), 둘 중 더 큰 것(최댓값)을 택하여 DP 배열을 최종적으로 갱신해주는 식으로 모든 줄을 반복하면 된다. 다만 주의할 것은, DP 배열을 초기화할 때, 음수 value값이 있으므로, 최댓값을 구하기 위해서는 0으로 초기화하지 않고, 나올 수 있는 가장 작은 값(-..

[백준] 1520. 내리막 길 - C++

[Gold III] https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 1 Bottom-Up 방식의 DP. 오른쪽 아래부터 왼쪽 위까지 채워나가는 방식으로 구현했다. 오른쪽과 아래로만 갈 수 있는 줄 알았는데, 위와 왼쪽으로도 갈 수 있어서 WA. #include #include #include #define init cin.tie(0)->ios_base::sync_with_stdio(0); typedef long long ll; using nam..

[프로그래머스] 코딩 테스트 공부 - 파이썬

2022 KAKAO TECH INTERNSHIP - 118668. 코딩 테스트 공부 [Lv. 3] https://school.programmers.co.kr/learn/courses/30/lessons/118668 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 보자마자.. DP로 접근해야 될 것 같은 문제라고 생각했다. [백준] 2342. Dance Dance Revolution - 파이썬 과 비슷한 느낌으로, Bottom-Up으로 풀면 된다. dp[alp][cop] => 특정 alp, cop를 달성하기 위한 최소 시간(cost) def soluti..

[백준] 2342. Dance Dance Revolution - 파이썬

[Gold III] https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 풀이 1 DP 문제라는 것은.. 보자마자 알겠음. [백준] 2281. 데스노트 가 생각이 나, 비슷한 방식으로, Top-Down 방식으로 풀려고 시도했으나.. line 12~13 부분에서 2의 제곱 형식으로 recursion이 계속 생길 거라.. 당연히 MLE나 TLE가 날 것이라고 예상했음. TLE. import sys sys.setrecur..