[코드트리 조별과제] 3주차 레포트

 

> 문제 풀이

# DP

📝 사각형 채우기 3 - https://www.codetree.ai/missions/2/problems/rectangle-fill-3/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제

정답률 27% 제출 1,427회 예상 소요 시간 91분

2 × n 크기의 사각형을 1 × 2, 2 × 1, 1 x 1 크기의 사각형들로 채우는 방법의 수를 구하는 프로그램을 작성해보세요

 
입력 예제

3

 
 
출력 예제

22

 
제출 결과

 
코멘트
- 사각형 채우기 유형이 여러가지 있지만, 1x1 짜리 블록이 포함된 다소 특이한 형태였다.
- 처음 점화식을 세울 때 이전 형태(목표보다 짧은 블록)에 양쪽으로 새로운 블록 패턴을 추가하는 아이디어를 떠올려서 더 헷갈렸다.

- 중복을 피하기 위해선 오른쪽에 추가하면서 늘리는 방식으로 생각해야 한다.

- 또한 가로 n- i 의 블록에 가로 i 크기의 블록을 더할 때, 중복을 피하기 위해선 다른 블록의 조합으로 만들 수 없는 고유한 i 크기의 블록 패턴만 사용해야한다.

- 고민을 해보면 가로 형태로 누운 2칸짜리 블록이 교차되는 형태로 각 크기별 고유한 블록이 2개씩 새로 생김을 알 수 있는데 2칸짜리 블록의 경우만 3개가 생기기 때문에 유의해야 한다(1x1 4개 패턴).

- 홀수 크기, 짝수 크기 상관 없이 모두 아래와 같은 패턴의 고유 패턴 2개씩.

- 크기 2x2 짜리 예외

 

# 그리디

📝 폭탄 해체 작업 - https://www.codetree.ai/missions/8/problems/the-bomb-dismantling/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제

정답률 36% 제출 351회 예상 소요 시간 159분

N개의 시한 폭탄이 있습니다. 각 폭탄을 해체하는데는 1 시간이 걸리며, 폭탄마다 해체하면 얻을 수 있는 점수가 있습니다. 각 폭탄마다 해체해야만 하는 시간 제한이 정해져 있으며, 시간이 다 되어 터진 폭탄은 이후 해체할 수는 없게 되지만 다른 폭탄 해체 작업에 영향을 주지는 않습니다. 폭탄 해체 작업은 모든 폭탄이 해체되거나 터질 때 까지 진행합니다. 폭탄을 해체해서 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성해보세요.

 
입력 예제

4
10 3
7 5
8 1
2 1

 
 
출력 예제

25

 
제출 결과

 
코멘트
- 이번 문제의 키포인트는 모든 폭탄의 해체 시간이 1로 동일하다는 것이다.

- 해체 시간이 달랐다면 풀이 방법이 달라졌겠지만, 동일하기 때문에 주어지는 정보 두 가지 측면에서 그리디하게 생각하면 된다.

- 먼저 점수 측면에서의 그리디 -> 현재 시간에 터지지 않은(해체가 가능한) 폭탄 중 가장 높은 점수의 폭탄이 최선의 선택이다.

- 시간 제한 측면에서의 그리디 -> 현재 가장 높은 점수의 폭탄을 가장 느리게 해체해야 이후 선택해야 할 폭탄들의 해체 가능 유무에 영향을 끼치지 않는다.

- 그렇다면 점수 순으로 정렬한 뒤, 정렬된 폭탄을 시간 제한에 최대한 가깝게 해체하는 방식으로 풀이하면 된다.

 

📝 자동차 단일 거래 이익 최대화하기 2 - https://www.codetree.ai/missions/8/problems/max-profit-of-single-car-2/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제

정답률 59% 제출 309회 예상 소요 시간 31분

향후 n년 간의 자동차 가격 정보가 미리 주어졌을 때, 자동차를 단 한 번 사서 되팔 때의 이익을 최대화하고자 합니다. 낼 수 있는 최대 이익을 출력하는 프로그램을 작성해보세요. 단, 자동차를 사기 전에는 팔 수 없습니다.

 
입력 예제

5
9 10 2 3 6

 
 
출력 예제

4

 
제출 결과

 
코멘트
- 이번 문제의 키포인트는 시점을 거꾸로 생각하는 것이다.

- 시간의 흐름에 따라 이익을 판단하면 시간 복잡도가 매우 커지게 된다.

- 우리는 미래를 알고 있다는 점을 인지하고, 시점을 거꾸로 타고 올라오면 된다.

- 현재 최대 자동차 가격보다 현재 시점의 자동차 가격이 낮다면, 그 차익만큼 이득을 추가하면 된다.

- 반대로 현재 시점의 가격이 더 높다면 현재 가장 비싼 자동차의 이득 측정을 멈추고, 현재 시점의 자동차 가격으로 업데이트하여 반복한다.