문제 11000 - 강의실 배정 접근 이전의 회의실 배정 문제와 비슷해보인다. 비슷해보이긴 하지만, 회의실 배정의 경우 최대한 많은 회의를 하도록 하는게 목표였다면, 이번에는 모든 강의를 진행해야 한다. 그 때 필요한 강의실을 최소화하는게 목표이다. 즉, 겹친다고 버릴 수 없다. 처음에는 쉽게 생각하고 강의실 배정 문제와 비슷하게 ...

문제 1931 - 회의실 배정 접근 그리디 알고리즘으로 해결할 수 있다. 회의 시간표를 끝나는 시간 기준으로 정렬한다. 끝나는 시간이 빠른 순서대로 회의를 잡아주면 항상 최적해이다. 특정 회의가 끝났을 때 시간을 기준으로 해당 시간보다 늦게 시작하는 회의들 중에서 가장 빨리 끝나는 회의를 진행한다. 이를 반복하면 항상 최대한 많은 ...

문제 1449 - 수리공 항승 접근 그리디 알고리즘으로 해결할 수 있다. 주어지는 위치를 정렬하고 앞에서 부터 테이프를 붙이면 된다. 시작점에 맞춰 테이프를 붙이면 항상 최적의 해를 만족한다. 코드 파이썬 코드 n, l = map(int, input().split()) arr = list(map(int, input(...

문제 11047 - 동전 0 접근 그리디 알고리즘으로 해결할 수 있다. 그리디 알고리즘은 특정 조건으로 선택했을 때 결과가 항상 가장 좋음을 보장할 수 있을 때 사용할 수 있다. 이 문제의 경우 동전들이 항상 이전 동전의 배수이며, 첫 동전은 1이다. 이는 가능한 가장 가치가 큰 동전을 사용했을 때 항상 최상의 결과를 보장해준다. ...

문제 무지의 먹방 라이브 접근 딱히 필요한 알고리즘은 없다. 당연하게도 k가 굉장히 크므로 k를 1씩 줄여가며 검사하면 효율성 테스트를 통과 못할 것이다. k를 빠르게 줄여나갈 방법이 필요하다. 우선 k가 주어지는 배열 원소의 합보다 크거나 같으면 k초 후에 먹을 음식이 없다는 의미이므로 -1을 리턴한다. 이제 본격적으로 k를 어떻게 ...

문제 9465 - 스티커 접근 DP 문제이다. i번 째 열에서 할 수 있는 행동은 스티커를 선택하지 않거나, 첫 번째 행의 스티커를 선택하거나, 두 번째 행의 스티커를 선택할 수 있다. 이를 모두 확인하기 위하여 DP 배열은 n x 3으로 설정하였다. DP(i, j) = i번째 열에서 j행의 스티커를 선택했을 때 최대 점수이다. j...

문제 11727 - 2xn 타일링 2 접근 DP 문제이다. 기존 타일링 문제가 조금 변형 되었다. DP[i-2]에서 DP[i]를 만드는 방법이 두 가지가 되었다. 기존에는 가로 타일 2개를 붙이는 방법만 존재했지만, 이제 2x2짜리 정사각형 타일을 붙일 수도 있다. 즉, DP[i]를 구할 때, DP[i-2]는 두배를 해주면 된다. ...

문제 11726 - 2xn 타일링 접근 DP 문제이다. 바로 앞에서 푼 문제랑 동일하다. 이 문제 역시 타일을 뒤에만 이어붙이는 식으로 해결한다. DP[i]는 DP[i-2]에 가로 타일 두개를 붙이거나, DP[i-1]에 세로 타일 한개를 붙이면 된다. 코드 파이썬 코드 n = int(input()) dp = [1] *...

문제 1904 - 01타일 접근 DP 문제이다. 문제 자체는 몇 개만 나열해보면 규칙이 나온다. 피보나치수열이다. 어떻게 피보나치 수열을 이루는 것일까? DP[i]는 i자리를 만드는 경우의 수이다. 그럼 DP[i]는 DP[i-2]의 경우들에 앞 뒤로 00을 붙이는 경우가 있을 수 있고, DP[i-1]에 앞 뒤로 1을 붙이는 경우가...

문제 2193 - 이친수 접근 DP 문제이다. 첫번째 자리는 항상 1이 와야한다. 그리고 이전 자리에 1이 나온 경우는 0밖에 올 수 없다. 이전 자리에 0이 나온 경우 0,1 모두 올 수 있다. 이를 정리하면, i-1번째 자리에 1이 나온 경우, i 번째 자리에는 0밖에 나올 수 없다. i-1번째 자리에 0이 나온 경우, i ...