코딩 테스트 5일차

4일차 복습

어린왕자가 장미꽃을 살리기 위해 행성을 최소한 들리는 방법이라는 문제이고

난 직선과 직선의 탄젠시한 각도를 구해서 별을 안 들리는 문제인 줄 알았는데 !! 아니었다!!

그냥 점을 포함하고 있는 행성의 개수를 확 확인하고 두 점을 모두 포함하는 행성의 개수를 측정하면 되는 것이었습니다.

 

결국 

if(Math.pow(x1 - cx, 2) + Math.pow(y1 - cy, 2) < Math.pow(r, 2) && Math.pow(x2 - cx, 2) + Math.pow(y2 - cy, 2) < Math.pow(r, 2)){ // 원과 점의 거리가 원의 반지름보다 작으면
      contectCount = 0;
      continue;
    }

출처: https://nicksoon.tistory.com/entry/코딩-테스트-4일차 [nicksoon:티스토리]

이걸 몰라서 틀린 문제이다 

 

5일차 시작

2000번

문제 : 상진이는 n개의 책을 담기 위한 책장을 만들려 한다. 그런데 상진이는 외관적인 문제 때문에 반드시 책장을 세개의 칸으로 구분하려 한다. 그런데 책장을 제작하는데는 많은 돈이 들기 때문에 책장의 크기를 최소화 하려 한다.

그런데 책장은 반드시 직사각형의 모양으로 이루어 져야 한다. 그렇다고 하였을 때, 책장의 크기는 다음과 같이 구할 수 있을 것이다. i번째 책의 높이와 두께를 각각 hi와 ti라고 하고, 첫 번째 책장에 들어가는 책의 집합을 S1, 두 번째 책장을 S2, 세 번째 책장을 S3 라고 하였을 때, 책장의 크기는 다음과 같은 식으로 구할 수 있다.

 

(그 무언가의 식)

 

이 식은 직관적으로 쉽게 알 수 있다. 각 칸의 높이는 그 칸에 들어있는 책들의 높이 중 가장 큰 높이가 될 것이고, 책장의 전체 넓이는 각 칸의 너비들 중 가장 큰 너비가 될 것이다. 그런데 각 칸의 너비는 최소한 그 칸에 들어있는 책들의 너비의 합이 되어야 하므로 위와 같은 식이 나오게 된다.

 

모르겠다 이건 1시간에 풀 수 있을까?

 

우선 1번 예제를 봤을때 

220 29

200 29 (195,20 / 200, 9)

180 30

이렇게 하니까 답인 18,000 이 나왔다 

 

그럼 폭이 넓은 것에 맞춰 개산 하나?

 

알고리즘 : 

- 다이나믹 프로그래밍?

- 그리디 알고리즘?

- 배낭문제

 

뭐지? 

 

우선 내가 생각한 것

책꽃이

 

빈칸에 모든 책들이 들어갈 경우의 수를 구한 후 책장의 넓이를 구하려고 했으나 

1. 71! 71팩토리얼의 값은 1.197857166996989e+113 즉 천문학 적인 수를 구해야 했다 

 

내일 다시 해봐야 겠다 ...