본문 바로가기
728x90

다이나믹프로그래밍30

[python] 백준 6198 옥상 정원 꾸미기 https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 문제 해결 stack 만으로 사용하기에는 시간초과가 걸려 dp를 이용함 for문을 통해 기준 빌딩을 잡은 가장 가까운 이전 빌딩부터 차례로 높이를 비교하여 더 큰 빌딩을 잡는다. 그 빌딩을 마지막으로 처음 빌딩부터 가장 긴 길이의 감소 수열 길이를 dp를 통해 저장한다. 그러면 기준 빌딩은 가장 긴 길이의 감소 수열 길이는 +1이고 그만큼의 정답이 늘어난다. 이것도 pypy3로는 통과 (p.. 2023. 4. 23.
[python] 백준 2482 색상환 https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 문제해결 원 안에서 이웃하지 않게 k개의 색을 고르는 문제 ( 원 순열은 아니고 원 조합도 아니고... 조건있는 원조합?) 규칙을 찾기는 어렵다. 1개 고를 때 부터 하면 n개의 색이 있는 경우 1개를 고르는 방법은 n가지 이다. 0개 고르는 방법은 1가지라고 하자. n개의 색이 있을 때 n-1까지 임의의 수 i는 i-1과 i+1의 색을 보면 되고 n은 n-1 1의 색을 봐야한다. dp[i][j]를 n개의 색중 1부터 .. 2023. 4. 18.
[python] 백준 1788 피보나치 수의 확장 https://www.acmicpc.net/problem/1788 1788번: 피보나치 수의 확장 첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제해결 |n| >1 일 때 F[n] = F[n-1] + F[n-2] 를 이용해서 새로운 수를 F 리스트에 넣는다. n을 음수로 확장시켰으 때 놀라운 규칙을 알면 끝이다. CODE n = int(input()) s = [0, 1] for i in range(2, abs(n) + 1): s.append((s[i - 1] + s[i - 2]) % 1000000000) i.. 2023. 4. 17.
[python] 백준 2240 자두나무 https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 문제 해결 정답이 이지선다형 문제이고 0, 1 둘 중 하나이다. 처음에 1을 선택하는 곳에 있다고 한다. 그러면 dp를 이용해 이동을 시키는 것을 목표로 한다. 처음에는 (w, t, answer) # 움직인 횟수, 시간, 정답 을 이용해서 dp[i][t]의 최댓값의 최댓값을 구하려고 했다. 하지만 움직인 횟수와 정답 선택간에 연관이 있었고 이를 표현하기 위해서는 오히려 더 간단한 코드가 편했다. (움직인 .. 2023. 4. 17.
728x90