본문 바로가기
728x90

그리디41

[python] 백준 1464 뒤집기 3 https://www.acmicpc.net/problem/1464 1464번: 뒤집기 3 세준이는 어떤 문자열 S를 뒤집으려고 한다. 문자열을 뒤집는 방법은 문자열의 길이를 N이라고 하자. i만큼을 뒤집는다는 소리는 그 문자열의 처음부터 정확하게 i개의 문자를 역순으로 뒤집는 www.acmicpc.net 문제 해결 간단해 보이지만 생각보다 간단하지 않은 문제 무조건 맨 왼쪽 문자부터 뒤집어야 한다는 규칙이 있다. 한 문자씩 왼쪽에서 오른쪽으로 볼 때 맨 뒤 혹은 맨 앞에 올 문자를 업데이트 한다고 보는 것이 편하다. 맨 앞에 올 수 있는 문자가 오면 그 앞에서 문자열 양 사이드 중 사전순으로 빠른 글자를 맨뒤로 오도록 뒤집은 다음 맨 앞에 올 수 있는 문자를 합하여 뒤집으면 된다. 사실 구현이 쉽지 않았.. 2023. 5. 11.
[python] 백준 1398 동전 문제 https://www.acmicpc.net/problem/1398 1398번: 동전 문제 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 초콜릿의 가격이 주어진다. 가격의 1015보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 동전이 1, 10, 25... 패틴을 확인 할 수 있는지 문제이다. 동전의 수열 집합을 A라 할 때 $A_{i}$ = 100$A_{i-3}$ 임을 확인 할 수 있으면 문제는 쉬워진다. 100 단위로 동전을 최대한 적은 수로 처리하는 방법을 생각하면 된다. CODE t = int(input()) coins = [1, 10, 25] # 이 형태로 계속 간다. for _ in range(t): x = int(input()) answer = .. 2023. 5. 10.
[python] 백준 2109 순회강연 https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 문제 해결 전형적인 그리디 문제 제안을 큰 p 순서, 작은 d 순서로 정렬을 시킨 다음 큰 p부터 최대한 늦게 스케줄이 비어 있는 날에 제안을 수락하려고 한다. 그러면 촉박한 d를 가진 것도 많이 할 수 있기 때문에 큰 값을 주는 순서대로 마감일자부터 가까운 날까지 확인하면서 계획이 없는 날에 강연을 하기로 하고 코드를 짜면 끝! CODE n = int(inpu.. 2023. 5. 8.
[python] 백준 1132 합 https://www.acmicpc.net/problem/1132 1132번: 합 N개의 수가 주어진다. 이 숫자는 모두 자연수이고, 알파벳 A부터 J가 자리수를 대신해서 쓰여 있다. 이 알파벳은 모두 한 자리를 의미한다. 그리고, 각 자리수는 정확하게 알파벳 하나이다. 0으로 www.acmicpc.net 문제 해결 알파벳에 숫자를 부여해서 주어진 문자의 합이 가장 크도록 만들기 단 한자리 알파벳이 주어졌을 때 그 알파벳은 0이 되면 안된다. 0이 안되는 알파벳을 어떻게 구현할까 고민했는데 True,False로 주어진 정보를 추가하는 수밖에 없는 것 같다. 구현은 어렵지 않다! CODE import sys input = sys.stdin.readline n = int(input()) alpha = [[0.. 2023. 5. 7.
728x90