본문 바로가기

greedy3

그리디 (2) BOJ17420 깊콘이 넘쳐흘러 '특정일에 사용하기로 정한 기프티콘'이 '기한이 가장 적게 남은 기프티콘'이여야만 사용할 수 있을 때, 한 번 연장할 때 30일씩 연장되는 기프티콘을 모두 사용하기 위한 최소 연장 횟수를 구한다. 1. 계획한 사용일자가 적게 남은 순으로 기프티콘 정렬 2. 정렬된 기프티콘의 사용 기한이 증가수열이 되도록 연장 2-1. 이때 사용일자가 같은 기프티콘이 있음에 주의 BOJ1898 이전 수열은 어떤 수열일까 1부터 N까지의 수를 나열한 수열 {Sn}이 주어질 때 모든 i(1≤i≤N)에 대해 | Si-Ai | < 2 인 수열 중 오름차순으로 나열할 때 가장 앞에 오는 수열 {An}을 찾는다. N=8일 때, 4자리에는 3,4,5,가 배치될 수 있지만 8자리에는 7,8만 배치할 수 .. 2021. 5. 31.
그리디 (1) BOJ14501 퇴사 N일간 잡힌 각 상담의 기간과 금액이 주어질 때 N일동안 상담으로 벌 수 있는 금액의 최댓값을 찾는다. 냅색 문제 같은 건데 N≤15라 단순히 시작/종료 시간 기준으로 최대 금액을 계산해 N²로 해결하면 된다. BOJ12904 A와 B A와 B로만 이루어진 문자열 S와 T가 주어질 때 S를 T로 바꿀 수 있는지의 여부를 구한다. 문자열 뒤에 A를 추가하거나, 문자열을 뒤집고 B를 추가하는 연산만 할 수 있다. 문자가 추가되는 위치는 A,B 관계없이 문자열의 가장 끝이므로 S→T로 생각하지 말고 T→S로 생각한다. BOJ8980 택배 N개의 마을과 마을 간 배송할 박스 정보 M개가 주어질 때 앞으로만 운행할 수 있고 용량이 C인 트럭으로 가장 많이 배송할 수 있는 박스 개수를 구한다... 2021. 5. 3.
BOJ2478 자물쇠 www.acmicpc.net/problem/2478 2478번: 자물쇠 처음 k-왼쪽밀기의 k를 첫째 줄에, (p,q)-구간뒤집기의 p와 q를 빈칸을 사이에 두고 둘째 줄에, 그리고 마지막 k-왼쪽밀기의 k를 셋째 줄에 출력한다. 만일 답이 여럿일 경우에는 그 중 하나만 출력 www.acmicpc.net 입력에 맞는 답 (k1, p, q, k2)가 여러 개 존재한다. 아래처럼 둘 중 뭐가 돼도 상관없다는 걸 먼저 파악함. 그 다음엔 가장 구하기 편한 걸 구하기로 했다. (3, 5, 7, 3): 12345678 → 45678123 → 45672183 → 72183456 (5, 3, 5, 1): 12345678 → 67812345 → 67218345 → 72183456 아래 여섯 가지 예시로 생각해보았다. .. 2021. 1. 7.

티스토리툴바