2024. 06. 19. ~ 2024. 06. 25.

백준 7 문제

 

1. BOJ 14654 : 스테판 쿼리 - S5

Implementation, Simulation 문제.

주어진 기록대로 시뮬레이션을 돌려서 푸는 문제였다. 

큐 같은걸로 시뮬레이션을 돌리는 문제.

 

 

2. BOJ 15084 : Treating Fractions Irrationally - S5

Implementation, Math, Arithmetic 문제.

나눗셈을 실제로 구현해서 돌리면서 0,9가 먼저 나오는지 아니면 주기성이 먼저 나오는지를 확인하는 문제였다.

n < d이므로 n * 10 / d 이렇게 몫을 구하고 n = (n*10) % d 이렇게 나머지로 n을 다시 업데이트 해주면서 나눗셈을 구현한다. 그러면서 주기성은 n * 10 가 이미 존재한 적이 있는지를 파악하면 된다.

주기 최대 길이가 d일 것이므로... (n은 %d 값을 취하니깐 n 값은 0 ~ d-1 사이의 값이 된다.) 시간복잡도는 O(d)일 듯.

 

3. BOJ 14731 : 謎紛芥索紀 (Large) - S1

Divide and Conquer, Math, Calculus 문제.

분할정복을 활용하여 2의 거듭제곱을 O(logK)만에 계산하고 결과값을 C * K 랑 같이 곱해서 더해준다.

총 시간복잡도는 O(NlogK).

 

4. BOJ 26091 : 현대모비스 소프트웨어 아카데미 - S1

나는 Multiset, Binary Search로 풀었다.

멀티셋의 lower_bound 메소드를 활용한다면 현재 남아있는 풀 중에서 제일 작은 값과 더했을 때에 M 이상이 되는 최솟값을 O(logN)만에 파악이 가능하다. (없다면 해당 값과 매칭해줄 수 있는 값이 없으므로 제외하면 된다.)

따라서 총 시간복잡도는 O(NlogN)인데, 다른 풀이로는 그냥 정렬 후 투 포인터를 하는 방법도 있는 것 같다.

아마 투 포인터 방법은 제일 큰 값 기준으로 더했을 때 M이 되는 최솟값을 찾도록 하는 방법일 듯. 

 

5. BOJ 13424 : 비밀 모임 - G4

Floyd-Warshall 문제.

모든 방의 쌍에 대해서 최단거리를 탐색하고 모든 방들 중에 각 친구들이 있는 방까지의 거리 합이 제일 최소인 방을 찾으면 된다.  각 친구들의 방에 대해서 다익스트라를 돌려도 풀 수는 있긴 하다.

각 테케별로 총 시간복잡도는 O(N^3). (K <= N 이라서 NK 는 N^3보다 작다.)

 

6. BOJ 30049 : 영업의 신 - G4

Implementation, Ad-hoc 문제.

각 매장별로 누적 매출액을 정렬된 상태로 관리할 수 있는 자료구조로 관리하면서 매장별 누적 매출 1위 직원이 누군지를 배열로 관리한다. 또한, 각 직원별로 누적 매출 1위를 한 매장 수를 배열로 관리하여 영업왕의 수가 처음에 몇 명인지를 확인한다.

이후에 각 쿼리별로 해당 매장의 누적 매출 1위가 변동될 때 누가 1등 했는지를 보면서 각 직원별로 누적 매출 1위를 한 매장 수를 업데이트 한다. 그러면서 영업왕의 수가 몇 명이나 바뀌었는지 확인하여 업데이트 하면 된다. 구현에 대해서 좀 생각해야하는 문제.

 

7. BOJ 30464 : 시간낭비 - G2

DP 문제.

dp[i][j]를 i번 턴 했을 때에 j번째 칸에 도달할 때 까지의 최대 거리라고 생각하자.

그렇다면 a[j]가 0 이상이므로 다음과 같이 식을 짤 수 있다.

dp[0]에 대해서는 dp[0][j+a[j]] = max(dp[0][j+a[j], dp[0][j]+1) 이렇게 j = 1..N-1까지 탐색,

dp[1]에 대해서는 dp[1][j-a[j]] = max(dp[1][j-a[j]], dp[0][j]+1, dp[1][j] + 1) 이렇게 j = N-1...1까지 탐색.

dp[2]에 대해서는 dp[2][j+a[j] = max(dp[2][j+a[j]], dp[1][j]+1, dp[2][j] + 1) 이렇게 j = 1...N-1까지 탐색.

이렇게 해서 dp[0][N], dp[2][N] 중 최댓값을 뽑아내면 된다.