2023.12.28.

[모두의 랜덤 디펜스] - 삼성 코딩테스트 (S1 ~ G1)

 

시험시간 : 180분, 실제 : 70분만에 올솔

Solved : 2/2

 

1. BOJ 13335 트럭 - S1

그냥 큐를 활용한 시뮬레이션 문제.

큐를 활용해서 각 시간마다 어느 차가 들어올 수 있는지를 시뮬레이션 하면 된다.

최대 걸리는 시간이 O(NW)일텐데 충분히 시간내에 돌아간다.

 

2. BOJ 23288 주사위 굴리기 2 - G3

빡구현 및 시뮬레이션 문제.

그래프야 뭐 BFS + Flood-fill을 해서 같은 숫자의 값들이 연속적으로 어떻게 붙여있는지를 파악하면 되어 어렵지 않았다.

그리고 시뮬레이션을 그냥 돌려도 될만한 K값이라 어렵지 않을 것 같았는데...

주사위 굴리는 구현이 제일 어려웠다.

첫 주사위 기준으로 동서남북을 잡아서 하드코딩하고, 전에 어느 숫자에서 어느 방향으로 왔는지를 고려해서 다음에 주사위 밑에 올 숫자를 알아내었다.

여기서만 한 시간정도 쓴듯.

 

백준 2문제

 

3. BOJ 1849 순열 - P5

세그트리 + 이분탐색 문제.

앞에 i보다 큰 숫자들의 개수를 세어야 하므로 1부터 N까지 순서대로 숫자를 집어넣어주면 되는데,

각 숫자별로 앞에 A[i] 만큼의 숫자가 들어갈 수 있는 공간을 주는 위치를 선정하면 된다.

그러면 나머지 숫자들은 항상 i보다 크므로 A[i]만큼의 큰 숫자들이 앞에 위치하게 된다.

그런데 위치를 선정하는 과정에서 앞에 자리가 어느정도 있는지를 파악해야 하는데, 전에 어느 숫자들이 들어가면 0, 비어있으면 1로 둔 배열에서의 세그먼트 트리를 생성하고 이분 탐색 쿼리로 O(logN)만에 위치 파악이 가능하다.

오랜만에 푼 세그트리 문제.

 

4. BOJ 1777 순열복원 - P5

BOJ 1849 기여창에 갔다가 알게된 다른 세그트리 + 이분탐색 문제.

전 문제와는 다르게 여기서는 역으로 자기보다 작은데 뒤에 있는 수들을 계산하므로 N...1 순서대로 집어넣어준다.

또한, 전 문제에서는 앞에서부터 A[i]개의 숫자가 들어갈 수 있는 위치를 선정해주었다면, 여기서는 역으로 뒤에 A[i]개의 숫자가 들어갈 수 있는 위치에 선정해야한다.

이외에는 전 문제와 똑같이 세그트리 + 이분 탐색으로 풀면된다.

 

오늘 일지는 여기서 끝.