https://www.acmicpc.net/problem/1455 코드import sysinput = sys.stdin.readlinen, m = map(int, input().split())board = [list(input()) for _ in range(n)]ans = 0for i in range(n-1, -1, -1): for j in range(m-1, -1, -1): if board[i][j] == '1': # 뒷면 # 뒤집기 for r in range(i+1): for c in range(j+1): board[r][c] = ('0' if board[r][c] == '1'..
문제풀이/Greedy
https://www.acmicpc.net/problem/1911 코드from math import ceilimport sysinput = sys.stdin.readlinen, l = map(int, input().split())woongs = []for _ in range(n): s, e = map(int, input().split()) woongs.append((s, e))woongs.sort()ans = 0prev = -1_000_000for i in range(n): if prev prev는 이전에 깔았던 널빤지 중 가장 끝의 널빤지의 끝 위치이다. 그렇기 때문에 prev가 현재 웅덩이의 시작위치보다 오른쪽이라면 prev에서부터 이어서 널빤지를 더 깔면 되고, 아니라면 현재 웅덩..
https://www.acmicpc.net/problem/2012 코드import sysinput = sys.stdin.readlinen = int(input())ranks = sorted(list(int(input()) for _ in range(n)))ans = 0for i in range(1, n+1): ans += abs(ranks[i-1]-i)print(ans) 무조건 예상 등수를 높게 적어낸 학생부터 높은 등수를 주어야 전체 불만도의 총합이 작아진다. 그러므로 예상 등수를 오름차순 정렬하여 그대로 등수를 부여하고 불만도를 구하면 된다.
https://www.acmicpc.net/problem/20115 코드n = int(input())drinks = list(map(int, input().split()))drinks.sort()ans = drinks[-1]for i in range(len(drinks)-1): ans += (drinks[i]/2)print(ans) 처음에는 남은 음료들 중 가장 양이 적은 2개를 골라서 합쳐야 하는줄 알았는데, 아니었다. 매 순서에 2로 나누어지는 음료들을 최대한 작게 해주어야 하는데, 이렇게 하면 그럴 수 없다.예를 들어, 음료 5개가 가장 작은 것부터 순서대로 a, b, c, d, e 이렇게 있다고 하면 원래 생각한 방법대로면 처음에 a, b를 뽑아서 (a/2)+b를 만들게 된다. 그 다음 순서..
https://www.acmicpc.net/problem/17451 코드import sysinput = sys.stdin.readlinen = int(input())v = list(map(int, input().split()))ans = v[-1]for i in range(n-2, -1, -1): if ans % v[i] != 0: ans = (ans//v[i]+1)*v[i]print(ans) 처음에 Parametric Search로 풀이했다가 시간 초과가 발생하였는데, Parametric Search 알고리즘만 하면 시간 복잡도가 O(logN)인데 조건 검사할 때마다 O(N)이 추가로 필요해서 그런 것 같다. 그래서 다시 살펴보니 Greedy로 풀이할 수 있을 것 같아서 바꾸었다. 행..
