문제 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 풀이 수식이 입력될 때, 괄호를 추가하여 최솟값으로 만들어 그 값을 반환하는 문제이다. 문제를 풀기 위해서는 입력된 값을 -를 기준으로 `split` 하고 좌측의 값들을 최대한 더한다. 그 후 우측의 값들을 빼주는 방식을 통해 문제를 해결할 수 있다. 코드 from sys import stdin if __name__ == '__main__': ex = stdin.readline().split('-') answer = sum(map(int, ex[..
문제 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한�� www.acmicpc.net 문제 풀이 양수 N이 주어졌을 때, 30의 배수가 되는 가장 큰 수로 만들어 반환하는 문제이다. 양수 N이 주어질 때 가장 큰 수가 되기 위해서는 각 자리별로 내림차순으로 정렬하여 큰 수가 앞에 오게 하면 된다. 또한 다음의 경우를 생각하여 30의 배수인지 확인하면 문제를 풀 수 있다. 주어진 숫자를 내림 차순으로 정렬한다. 끝자리가 0이 아니라면, 30의 배수가 될 수 없으므로 -1을 반환한다. 끝자리가 0이 아닌 것으로 10의 배수가 되는지 확인하였으므..
문제 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 병든 나이트가 N, M 크기의 체스판을 이동할 때, 방문할 수 있는 칸의 개수의 최대 값을 반환하는 문제이다. 문제를 처음 접하였을 때는 BFS로 푸는 건가? 하고 생각을 했다. 하지만 N, M은 2,000,000,000까지 이므로 최대 값이 입력된다면 시간 내에 통과할 수 없게 된다. 문제를 풀기 위해서 병든 나이트의 이동에 대해 생각해보면, 좌측으로 가지 않고 반드시 우측으로 이동한다는 특징을 가지고 있다. 또한 방문한 칸이 5개 미만인 경우에는 이동 방법에 대한 제약이 없다는 특징을 가지고 있다. 위의 특..
문제 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 문제 풀이 앞서 푼 문제들 중에 이 문제와 유사한 문제들을 다루었다. 가장 긴 증가하는 부분 수열 가장 긴 증가하는 부분 수열 4 가장 큰 증가 부분 수열 가장 긴 감소하는 부분 수열 가장 긴 바이토닉 부분 수열 하지만 이 문제는 위의 문제들과 달리, N의 크기가 최대 1,000,000으로 위의 문제를 해결한 방식으로 풀고자 하면 시간 초과가 발생한다. 앞서 다룬 문제들은 시간 복잡도가 O(N^2)이 걸리게 된다. 따라서 순열을 탐색하는 데 있어 시간을 최적..
문제 2109번: 순회강연 한 저명한 학자에게 n(0≤n≤10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1≤d≤10,000)일 안에 와서 강연을 해 주면 p(1≤p≤10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에� www.acmicpc.net 문제 풀이 강연을 할 수 있는 경우에 따라, 시간과 일수가 정보로 주어진다. 문제를 풀기 위해서는 `heapq`를 사용하면 쉽게 해결할 수 있다. 입력된 정보(강의료, 일정)를 일정 순으로 정렬하고, heap에 있는 값의 수를 일정이라고 생각하여 처리하면 쉽게 풀 수 있다. 코드 from sys import stdin import heapq if __name__ == '__main__': PAY, DAY = 0, 1 answer ..
문제 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제 풀이 보석점에 각 보석에 대한 무게와 가격이 주어진다. 또한, K개의 가방에 각각 담을 수 있는 무게가 정해져 있다. 이때 훔칠 수 있는 보석의 최대 가격을 구하는 것이다. 이 문제는 평범한 배낭과 달리, heap을 이용하여 푸는 문제이다. heap의 성질과 Python에서 사용되는 `heapq`를 이해하고 있다면 어렵지 않게 풀 수 있다. 보석과 가방을 무게 순으로 정렬한다. 가방의 무게 ..
백준: 1080 행렬
문제 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 문제 풀이 행렬이 주어 질 때, 3 * 3 크기에 해당하는 부분을 반전시킬 수 있다. 이때 행렬 A, B가 같아질 수 있도록 하는 최소 연산 값을 구하고 구할 수 없다면 -1을 반환한다. 예제 입력 1의 경우 아래의 그림과 같이 2번의 시도로 B와 같게 만들 수 있다. 여기서 주의 할점이 있다면, 변경하고자 하는 위치가 B와 다른 경우에만 반전시키고 그렇지 않은 경우는 반전시키지 않아 B와 유사한 형태로 나아갈 수 있도록 해야 한다는 것이다. 코드 from sys imp..
문제 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 풀이 돈을 인출하는데 시간이 짧은 사람부터, 우선적으로 처리하는 것이 누적 시간을 줄이는 방법이다. 따라서 인출하는데 걸리는 시간을 정렬한 후에 자신의 차례 이후에 남은 사람의 수만큼 곱하면 누적 시간을 계산할 수 있다. 예를 들어 1, 2, 3, 4 순으로 돈을 인출한다고 하면 4 + 6 + 6 + 4와 같이 총 20의 시간이 소모된다는 것을 계산할 수 있다. 이는 뒤에 있는 사람은 앞의 인출 시간에 영향을 받는 것을 반영한 것이다. 코드 from sys import stdin i..
