CEO

문제 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..

문제 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 풀이 특정 금액 K가 주어질 때, 동전으로 변환할 경우 최소한의 동전으로 나타내는 동전의 수를 반환하는 문제이다. 이를 해결하기 위해서는 동전 중 금액이 가장 큰 동전부터 순회하며, 현재 금액인 K보다 작다면 `divmod`를 활용하여 몫은 동전의 수, 나머지는 잔돈이 되므로 이를 갱신하며 반복하면 된다. 코드 from sys import stdin if __name__ == '__main..

문제 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 풀이 회의가 끝나는 시간이 짧은 순서대로 정렬한 후에, 회의가 시작하는 시간이 짧은 순서대로 정렬하여, 회의를 할 수 있는지 하나씩 확인하는 방식으로 문제를 풀 수 있다. 처음에 문제를 풀 때는, 단순히 끝나는 시간이 가장 짧은 것만 파악하여 처리하면 된다고 생각하고 제출하였는데.. 90% 이상쯤에서 틀렸습니다. 를 만나게 되었다. 가만히 생각해보니, 가장 짧은 시간과 함께 시작 시간도 고려야 해야 되는 것이 빠졌다는 것을 알고 정렬을 `x: (x[1], x[0])` 과 같이 하니 맞았습니다!! 를 볼 수 있었다. 코드 from sys import stdin if __..

문제 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으� www.acmicpc.net 문제 풀이 (0, 0)에서 출발하여, (m - 1, n - 1)에 도착하는 경우의 수를 구하는 문제이다. 문제의 조건은 더 낮은 지점으로만 이동할 수 있으며, 가능한 경우의 수를 모두 구하여야 한다. 이 문제를 풀기 위해 단순히 BFS, DFS를 사용하면 각 경로를 탐색하기 위해 중복으로 탐색할 가능성이 크다. 따라서, 재귀 호출을 통해서 방문 가능한 경로의 수를 반환하고, 한번 탐색한 경로는 더 이상 탐색하지 않도록 하는 방법을 사용하여야 시간 초과를 발생시..

문제 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 � www.acmicpc.net 문제 풀이 이전에 다룬 단지번호붙이기, 섬의 개수와 유사한 문제이다. 다른 점이 있다면 비가 오는 양에 따라 침수되는 지역이 달라지며, 그로 인해 안전 영역의 개수가 변동된다는 것이다. 문제를 풀기 위해서는 BFS로 탐색을 하되, 높이가 가장 낮은 곳이 침수될 때부터, 가장 높은 곳이 침수될 때까지 BFS를 탐색하여 영역의 개수를 구하고 최대 값을 반환하면 된다. 3중 반복문을 통해 BFS를 호출한다. 첫 번째 반복문 : 가장 낮은 높이 ~ 가장 높은 높이 두..

문제 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 풀이 수열이 주어지고, 수열 중 일부를 선택할 때 선택한 부분이 회문(Palindrome)인지 여부를 반환하는 문제이다. 이 문제를 풀기 전까지는 시간이 충분히 주어지는 회문 문제들을 풀어서, 단순히 list를 조작하는 방식으로 회문을 찾았다. 하지만 이 문제는 그런 식으로 풀면 시간 초과가 발생한다. 다른 DP 문제들과 마찬가지로, 메모이제이션을 통해 길이가 1부터 N까지의 늘려가며 회문인지 여부를 리스트에 기록해두는 방식을 사용한다. 다음과 같이 지정된 범위에 따라 회문의 여부를 결정할 ..

문제 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 풀이 기존에 풀었던 퇴사 문제에서 N의 범위가 커진 문제이다. N의 범위가 커짐에 따라 DFS로 풀지 않고 DP로 풀어야 문제를 해결할 수 있다. 즉 최대 수익을 완전 탐색을 통해 찾지 않고, 메모이제이션을 통해 값을 누적시켜가며 N일 까지 진행시켜야 한다. 점화식은 현재 날짜 + 일하는데 필요한 날짜

문제 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀�� www.acmicpc.net 문제 풀이 숫자가 주어 질 때, +, - 를 통해 숫자를 계산 할 수 있으며 계산된 숫자의 범위는 0 보다 크고, 20 보다 작아야 한다. 또한 주어진 숫자를 계산할 때, 마지막으로 주어진 숫자와 일치해야 한다. 예제 입력1의 경우 문제의 주어진 힌트와 같이 다음과 같은 경우의 수가 있다. 8+3-2-4+8-7-2-4-0+8=8 8+3-2-4+8-7-2-4+0+8=8 8+3+2+4-8-7+2-4-0+8=8 8+3+2+4-8-7+2-4+0+8=8 ..