UP

문제 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성..

문제 풀기 : 1744번 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 문제 길이가 N인 수열이 주어졌을 때, 수열의 두 수를 묶고 수열의 합을 구한다. 위치에 상관없이 수를 묶을 수 있다. 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 묶은 수는 서로 곱한 후에 더한다. 예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2x3)+(4x5) = 27이 되어..

문제 풀기 : 1931번 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만든다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있다. 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾는다. 단, 회의는 한번 시작하면 중간에 중단될 수 없다. 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. (이 경우에는 시작하자마자 끝나는 것으로 생각한다.) 문제풀이 최적의 해를 구하는 그리디 문제이다. 회의실을 최대로 사용하려면 회의가 끝나는 시간이 짧은 순..

문제 풀기 : 11399번 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우 [1, 2, 3, 3, 4] 순으로 출력하면 각 사람이 돈을 인출하는데 필요한 시간의 합은..

문제 풀기 : 1783번 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다. 2칸 위로, 1칸 오른쪽 1칸 위로, 2칸 오른쪽 1칸 아래로, 2칸 오른쪽 2칸 아래로, 1칸 오른쪽 병든 나이트는 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이..

문제 풀기 : 10610번 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 문제 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수 만든다. 단, 수가 존재하지 않으면 -1을 출력한다. 문제풀이 최적의 해를 구하는 그리디 문제이다. 숫자들의 위치를 바꿔서 30의 배수가 되는 수 중 가장 큰 수를 찾으면 된다. 30의 배수가 되려면 첫째, 마지막 자리수가 0이어야 한다. 둘째, 3의 배수는 각 자리의 숫자 합이 3으로 나누어 떨어진다. 코드 TIP ''.join(배열) : 배열을 문자열로 바..

문제 풀기 : 2875번 2875번: 대회 or 인턴 첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N), www.acmicpc.net 문제 2명의 여학생과 1명의 남학생이 팀을 결성해서 나간다. N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다. 만들 수 있는 최대의 팀 수를 구한다. 문제풀이 최적의 해를 구하는 그리디 문제이다. 각각의 N명, M명에서 여학생이 2명, 남학생이 1명을 빼면서 팀을 결성한다. K명의 인턴쉽 참가자가 필요하기 때문에 팀을 결성하고 남은 N + M명이 K보다는 클 때 만든다는 조건을 ..

문제 풀기 : 11047번 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 문제 준규가 가지고 있는 동전은 총 N종류이다(각각의 동전을 매우 많이 가지고 있다.) 동전을 적절히 사용해서 동전의 합을 K로 만들려고 한다. 이 때 필요한 동전 개수의 최솟값을 구한다. 문제풀이 최적의 해를 구하는 그리디 문제이다. 동전의 합을 크게 만들기 위해선 동전의 종류 중 가치가 큰 동전의 필요한 개수부터 빼나가면 된다. 전체코드 # n : 동전의 종류 수, k ..