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

링크 https://www.acmicpc.net/problem/1041 난이도(solved.ac 참고) 골드5 풀이 이 문제를 처음 봤을 때는 이게 뭐지? 왜 실버1이지? 걍 브론즈급인데 라고 생각했는데 풀어보니 그게 아니었다. ㅋㅋ 주사위의 최상단 면 + 그 면과 접한 최상위층 면의 합: (최소값) * n^2 + (두번째 작은 값) * 4(n-1) + (세번째 작은 값) * 4 (예를 들면, 3의 경우 최상단 면 9개 + 그 9개와 접해있는 12개의 면) 나머지 면들의 합: ((최소값) * 4(n-1) + (두번째 작은 값) * 4) * (n-1) 이 식 구하는 건 별로 어렵지 않다. 그냥 2 3 4인 경우를 머릿속에 그려보고 하면 금방 나온다. 근데 문제는, 주사위에는 ABCDEF로, A는 F와 마주..

링크 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/2217 난이도(solved.ac 참고) 실버3 풀이 문제 풀이 방법은, 그냥 내림차순으로 나열한 다음에 a_list[인덱스] * (인덱스+1)의 최댓값을 구하면 끝난다. a_list[인덱스]는, 예제의 경우 내림차순하면 15 10 이 되는데, 각 로프에 모두 고르게 중량이 걸리게 되므로 15를 선택한다면 15만큼만 들 수 있고, 10을 선택한다면 (10 * 2) = 20만큼 들 수 있다. 이 생각을 토대로, a_list[인덱스]의 값은 작아지고 인덱스는 커지는 상황에서 결국 들 수 있는 값인 a_list[인덱스] * (인덱스 + 1)의 최댓값을 구한 것이다. (여기서 인덱스+1을 해 준 이유는, 인덱스는 0부터 시작하기 때문이다.) 사실 어..

링크 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)에도 해당한다. ..

문제 기술 n(1이상 1000이하 정수)개의 지하철 역(0부터 n-1까지 번호가 붙여져 있음)과 인접한 역의 쌍들이 주어져 있다. 두 지하철 역 a와 b에 대하여 a로부터 b로 가는 가장 짧은(지나는 에지 수가 가장 작은) 경로의 길이(지나는 에지의 수)를 구하는 프로그램을 작성하시오. 요구조건: 지하철 망을 인접리스트로 나타내고, 탐색방법은 너비우선탐색을 이용한다. 입력 첫 번째 줄에 지하철 역 수 n(1이상 1,000이하 정수)이 주어지고 두 번째 줄에 인접한 역들의 쌍의 수 m(0이상 30,000이하 정수)이 주어진다. 다음 m 개의 각 줄에 인접한 두 역 번호(0이상 n-1이하 정수가 빈칸을 사이에 두고 주어진다. 마지막 줄에 두 지하철 역 번호 a, b가 주어진다. n m // 지하철 역 수, ..