본문 바로가기
728x90

알고리즘316

[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] 백준 1508 레이스 https://www.acmicpc.net/problem/1508 1508번: 레이스 첫째 줄에 N, M, K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, M은 K보다 작거나 같다. 또, K는 2보다 크거나 같고, 50보다 작거나 같다. 둘째 줄에 심판이 있을 수 있는 K개의 위치가 주어 www.acmicpc.net 문제 해결 combination으로 모든 경우의 수를 체크하려 했지만 $ 50 \choose 25$ 와 같이 경우의 수가 큰 경우는 시간초과 난다. 경우의 수가 생각이 안나서 인터넷에서 다른 사람들의 풀이를 참고하였다. 이진탐색으로 가장 짧은 길이의 최대 길이를 만들어서 정답을 구할 수 있었다. 가장 짧은 길이를 start(=0), 가장 길 수 있는 길이를 end-1로 놓.. 2023. 4. 16.
[python] 백준 1371 가장 많은 글자 https://www.acmicpc.net/problem/1371 1371번: 가장 많은 글자 첫째 줄부터 글의 문장이 주어진다. 글은 최대 50개의 줄로 이루어져 있고, 각 줄은 최대 50개의 글자로 이루어져 있다. 각 줄에는 공백과 알파벳 소문자만 있다. 문장에 알파벳은 적어도 하나 이 www.acmicpc.net 문제 해결 문제를 해결하는 방식은 전체 문자열을 이어붙여서 나오는 알파벳 양이 많은 것을 리스트에 넣고 sort() 정렬시키면 될 것이다. 하지만 문장이 50줄 이하라는 것만 알고 몇줄이 주어질지 모르는 상황에서 input을 어떻게 하는지 어려웠다. 정답은 input= sys.stdin.read를 통해 조건없는 문자열 개수를 입력할 수 있다는 것을 알 수 있었다. CODE import sy.. 2023. 4. 14.
[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.
728x90