본문 바로가기
728x90

다이나믹프로그래밍30

[python] 백준 2229 조 짜기 https://www.acmicpc.net/problem/2229 2229번: 조 짜기 알고스팟 캠프에 N(1 ≤ N ≤ 1,000)명의 학생들이 참여하였다. 학생들은 열심히 공부를 하고 있었는데, 어느 날 조별 수업을 진행하기로 하였다. 조별 수업의 목적은 잘 하는 학생들과 덜 잘 하는 www.acmicpc.net 문제 해결 사실 딱히 좋은 아이디어가 생각이 안났다. DP를 이용해 풀어야 겠다는 생각을 했는데 사실 시간복잡도가 커서 마음이 안들었다. import sys input = sys.stdin.readline INF = sys.maxsize n = int(input()) A = list(map(int, input().split())) # value: 점수 index: 나이 dp = [0]*(10.. 2023. 4. 16.
[python] 백준 15486 퇴사2 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를 어떻게 쓸지 처음에 막막했다. dp[i]를 i 번째 요일까지 일 했을 때 최대 이익이라고 정의하고 M을 통해 실시간으로 최대 이익을 계산하면 된다. CODE import sys input = sys.stdin.readline n = int(input()) time, point = [], [] dp = [0]*(n+1) for i in range(n):.. 2023. 4. 16.
[python] 백준 11060 점프 점프 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 문제 해결 판에 써져 있는 수 이하만큼 이동을 해서 최소한의 이동으로 끝까지 가는 문제 사실 bfs를 쓰고 이동을 1~판에 써져 있는 수 로 해서 바로 끝냈지만 메모리가 초과 되었다.(아무래도 MAX 이동 가능 거리가 100이기 때문에 많은 경우의 수가 deque로 들어가는 경우가 있기 때문) 그래서 어떻게 조건을 주어서 que에 들어가는 양을 줄일까 생각을 했는데 DP였다. DP로 이.. 2023. 4. 13.
[python] 백준 9082 지뢰찾기 https://www.acmicpc.net/problem/9082 9082번: 지뢰찾기 지뢰찾기 게임은 2×N 배열에 숨겨져 있는 지뢰를 찾는 게임이다. 지뢰 주위에 쓰여 있는 숫자들로 지뢰를 찾을 수 있는데, 한 블록에 쓰여진 숫자는 그 블록 주위에 지뢰가 몇 개 있는지를 나타 www.acmicpc.net 문제해결 상당히 복잡해 보이지만 한 번 이해하면 간단하다. 우선 지뢰가 확실히 있는 곳을 통해 블록의 주위에 개수가 몇개 있는지를 최신화 한다. 그리고 왼쪽부터 오른쪽으로 가면서 블록주위 숫자가 모두 숫자가 0이 아니면 1개를 추가하고 블록의 주위 개수를 1씩 줄여주면 된다. CODE t = int(input()) for _ in range(t): n = int(input()) graph = [] g.. 2023. 4. 13.
728x90