링크 https://www.acmicpc.net/problem/1946 난이도(solved.ac 참고) 실버1 풀이 이 문제를 처음 보고, 서류심사 성적(첫번째 숫자)을 기준으로 sort한 다음에, 첫 값을 고정으로 두고 더 작은 값을 heap에 넣는 것까지는 바로 생각을 했는데, heap에 넣게 되는 값 기준으로 그 다음 것들과 비교를 해야 되었기 때문에 그렇게 하는 방법에 고민을 좀 했다. 생각해 본 결과, 현재 위치인 now에 처음에는 첫 숫자를 대입하고 더 작은 값을 찾은 경우에 heap에 넣으면서 동시에 now를 그 값으로 대체해 주면 되었다.

링크 https://www.acmicpc.net/problem/11000 난이도(solved.ac 참고) 골드5 풀이 회의실 배정과 비슷하지만 좀 다른 문제이다. 회의실 배정은 한 개의 회의실만 있는 상태에서 할 수 있는 회의의 최대값을 구하는 것이었던 반면에, 강의실 배정은 주어진 모든 강의를 할 수 있도록 하는 강의실 수의 최소값을 구하는 문제이다. 후술하겠지만 시간 초과가 떠서 애를 좀 먹었다. 힙을 써야겠다고 생각하여 우선 첫 번째 강의의 종료 시간을 heap에 넣은 다음에 그 값과 다음 강의의 시작 시간을 비교해서 만약 다음 강의의 시작 시간이 더 이르다면, 결국 강의실이 하나가 더 필요하게 된다. 두 번째 강의를 시작하려고 보니 아직 첫 번째 강의가 끝나지 않아서 강의실을 새로 구해야 하기 때..

링크 https://www.acmicpc.net/problem/1931 난이도(solved.ac 참고) 실버2 풀이 이 문제를 풀면서 lambda를 처음 사용해봤다. 알고리즘 수업을 들으면서 회의실 배정 문제를 이론으로만 접했었는데, 당시에 끝나는 시간이 빠른 순서대로 하는 것이 최적의 결과를 가져온다는 것을 깨닫고 lambda 함수를 이용하여 끝나는 시간인 x[1]을 기준으로 나열했고, 2순위로는 시작 시간인 x[0]을 기준으로 나열했다. 여기서, 왜 2순위로 시작 시간을 뒀는가? - 이부분은 예시로 들어서 설명해야 한다. 2 3 3 1 3 이런 예시가 있다고 하자. 이 경우에 2순위로 시작시간을 나열하지 않는다면 3 3이 먼저 실행이 되고, (3 3)의 뒷자리보다 (1 3)의 앞자리가 더 작기 때문에..

링크 https://www.acmicpc.net/problem/11047 난이도(solved.ac 참고) 실버2 풀이 그리디의 대표 문제이다. k에서 i를 나눈 몫을 count에 더해주고, k를 i로 나눈 나머지를 k에 지정한다. 위 예제 입출력을 예시로 들어서 설명해보겠다. 현재 k는 4200원이고, 리스트에는 1원부터 5만원까지의 금액이 있다. 4200원은 5천원~5만원으로 나눴을 때는 몫이 0이다. 천원으로 나눴을 때 비로소 몫이 발생한다. 그래서, i가 1000일 때 k를 i로 나눈 몫을 count로 지정을 해 주는 것이다. 이렇게 되면 count는 천원짜리 네 개가 추가되어 4가 되고, k는 4200 % 1000 = 200원이 된다. 이와 같은 계산을 반복하는 것이다. 4200 -> 200 ->..

링크 https://www.acmicpc.net/problem/14241 난이도(solved.ac 참고) 실버2 풀이 합치는 두 슬라임을 합한 값이 새로운 슬라임이 되고, 전체 점수는 합치는 두 슬라입을 곱한 값이므로 총 점수 값에 (지금 값 * 다음 값)을 넣어준 뒤 두 개를 더한 값을 i번째 인덱스에 두고 i+1번째의 값을 삭제했다. 이렇게 하면 곱한 값은 계속 더해지고, 더한 값은 0번째 인덱스에 계속 업데이트 되면서 그럴 때마다 다음 인덱스가 삭제된다. 결국 while문의 조건에 따라 값이 하나만 남았을 때 종료하고 그 때의 총 점수를 출력함으로써 해결하였다.

링크 https://www.acmicpc.net/problem/9237 난이도(solved.ac 참고) 실버5 풀이 좀 허무했다. 처음에 내가 너무 어렵게 생각했는데, 이게 실버5가 맞나..? 라는 생각이 들어서 일단 접어뒀다가 다시 풀고 금방 맞았다. 이 문제에서의 핵심은, 총 걸리는 시간은 배열 내 최대값 + 그 인덱스의 값이기 때문에, 큰 값을 가장 앞에 둬야 된다는 것이다. 큰 값이 뒤에 있다면, 이미 인덱스가 많이 증가한 상태이기 때문에 결국 최종 걸리는 시간은 더 길어지게 된다. t 배열에 각자 다 자라는데 며칠이 걸리는지에 대한 값을 넣었고, 그 값을 내림차순으로 정렬했다. 그렇게 되면, 다 자라는 데 오래 걸리는 묘목을 앞 순서에 배치시켜서 묘목이 자라는 데 걸리는 시간 외에, 그 묘목을 ..

링크 https://www.acmicpc.net/problem/11399 난이도(solved.ac 참고) 실버3 풀이 이 문제는 처음에 봤을 때부터 어떻게 풀어야 할 지 바로 머릿속에 떠올랐다. 가장 시간이 적게 들게 하려면, 걸리는 시간을 sort하여 가장 작은 값이 맨 앞에 오도록 해야 한다. 그래야 오래 걸릴수록 뒤로 가서, 전체 시간(돈 뽑는 시간 + 대기시간)을 줄일 수 있기 때문이다. 우선 배열 m을 sort했고, 각 사람들의 소요시간 process_time, 전체 소요시간 total_process_time을 각각 배열, 숫자 로 선언했다. 첫 번째 사람은, 기다리는 시간이 없기 때문에 돈을 뽑는 시간 m[0]만 더해주고, 이는 전체 소요시간(total_process_time)에도 해당한다. ..

문제 기술 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. 문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오. 입력 첫째 줄에 문..