랜덤 마라톤 14주차

 

A. Card Game Contest (백준 14551)

조합론

 

각각의 덱은 독립적이므로 총 방법의 수는 $A_1$부터 $A_N$까지 곱하면 된다. 단, 덱이 없을 수도 있는데, 이때는 스킵하거나 0을 1로 바꾸면 된다. $M$으로 나눈 나머지를 구해야 하므로 곱할 때마다 모듈러 연산을 취해주면 된다.

 

 

---

B. 행사장 대여 (Small) (백준 14732)

구현

 

범위가 작으므로 좌표를 받을 때마다 그 부분의 영역들을 2차원 배열에 1로 채워주면 된다. 이후 넓이를 구할 때 1의 개수를 세어주면 된다.

 

---

C. 체크포인트 달리기 (백준 29891)

그리디, 정렬

 

일단 들어오는 모든 수가 양수 혹은 음수일 때를 생각해보면, $N$이 $K$의 배수라면 거리가 먼 순서부터 체크하던지, 가까운 순서부터  체크하던지 상관없지만 아니라면 $K$개씩 체크포인트를 체크하다가 $K$보다 작게 체크포인트를 찍어야 하니 이동거리를 최소화하기 위해서 이 상황에서는 가까운 위치에 체크하는 것이 최소화 하는 방법이다. 그러면 결국은 가장 먼 거리부터 체크해주면 된다는 의미다. 만약 양수, 음수가 모두 들어온다면 따로 해주면 된다. 양수 -> 음수 혹은 음수 -> 양수 위치로 갈 때 반드시 0을 지나야 하기 때문에 따로 확인해줘도 된다.

 

---

D. Hot Air Ballooning (백준 13915)

셋, 정렬

 

들어오는 수를 각각의 원소로 나누어 저장하고, 중복 제거하고 정렬을 해줬다. 정렬을 해주지 않으면 134와 143은 다른 수가 되어버리므로 정렬을 해서 똑같은 수임을 명시하기 위해서다. 다른 방법도 있겠지만 이게 생각하기 편했다. 그리고 set에 저장한 후 set에 있는 원소들의 개수를 출력하면 된다.

 

---

E. 안정적인 문자열 (백준 4889)

스택

 

먼저 {}는 안정적인 문자열이므로 스택을 이용해서 제거한다. 모두 제거한 후 스택에 남아있는 문자들을 어떻게 처리할지 생각하면 된다. 항상 길이가 짝수인 문자열이 들어오기 때문에 스택에서 제거했던 것들도 모두 짝수 개만큼 제거되었으니 스택에 남아있는 문자들의 개수도 짝수다. 스택에서 2개의 문자를 뺀 후 2가지 방법을 떠올리면 된다.

 

첫 번째는 두 개의 문자열이 서로 같은 경우다. '{', '{'로 되어 있는 경우는 뒤의 문자를 '}'로 바꾸면 안정적인 문자열이 되고, '}', '}'인 경우는 앞의 문자를 '{'로 바꾸면 된다. 즉 바꾸기 연산을 1번 하면 된다.

두 번째는 서로 다른 경우이다. '{', '}'인 경우는 이미 안정적인 문자열이므로 처음 스택 부분에서 제거 되었으니 스택에 저장되어 있지 않다. 다르게 말해서 '}', '{'인 경우 밖에 없는데 앞 문자를 '{'로 변경하고, 뒷 문자를 '}'로 변경해야 하니 바꾸기 연산을 2번 해야한다.

 

---

F. 아름다운 수열 (백준 21605)

구성적

 

$B_i$를 몇 개만 풀어 써보자.

 

$B_1$ = $0 \times A_1 + A_2 = A_2$

$B_2$ = $B_1 \times A_3 + A_4 = A_2A_3 + A_4$

$B_3$ = $B_2 \times A_5 + A_6 = (A_2A_3+A_4)A_5 + A_6 = A_2A_3A_5+A_4A_5 + A_6$

$B_4$ = $B_3 \times A_7 + A_8 = (A_2A_3A_5+A_4A_5 + A_6)A_7 + A_8$ $=$ $A_2A_3A_5A_7+A_4A_5A_7 + A_6A_7$ $+ A_8$

 

$B_4$를 기준으로 $\underbrace{A_2A_3A_5A_7}_{\text{4 counts}} + \underbrace{A_4A_5A_7}_{\text{3 counts}} + \underbrace{A_6A_7}_{\text{2 counts}} + \underbrace{A_8}_{\text{1 count}}$ 대충 $A_i$ 개수가 1씩 늘어난다. 이 규칙이 중요한 건 아니고, 개수가 짝수인지 홀수인지로 판단해서 $1$인지 $-1$인지 생각하기 위해서다. 일단은 가장 크게 만들어야 하니 $A_8 = 1$이라 생각하고 $A_6A_7 = 1$을 만들기 위해서 둘 다 $1$을 할 것인지, 둘 다 $-1$을 할 것인지 결정해야 한다.

둘 다 $-1$을 선택한다면, $A_4A_5A_7$의 경우는 $A_7$이 이미 $-1$이므로, $A_4$와 $A_5$는 달라야 한다. 나는 $A_6$을 이미 $-1$라 둬서 $A_5$도 $-1$로 둠으로써 연속적으로 $3$개가 $-1$이 되었다. 그러면 $A_4$는 $1$이 되고, $A_2A_3A_5A_7$에서 $A_2A_3$을 $1$로 만들면 되니 둘 다 $1$로 정하므로써 또 연속적으로 $3$개가 $1$이 된다. $A_1$은 무엇이든지 간에 영향을 주지 않으므로 커스텀 해주면 된다. 커스텀 해줘야 하는 부분은 규칙을 보면 $2N$에서 $3$을 나눴을 때 나머지가 $2$인 경우에 이 규칙으로 하면 $1$과 $-1$이 같지않고 $2$ 차이가 나서, $A_1$을 다른 수로 교체하면 개수가 정확히 반이 된다.

 

---

G. 벼락치기 (백준 29704)

냅색

 

dp 테이블을 dp[마감 일까지 남은 일 수] = 벌금의 합의 최대로 정의했다. 만약 dp[2] = 8000이면, 현재 마감일까지 2일 남았고, 벌금 8000원을 내지 않아도 된다는 의미이다. 이 경우는 그냥 냅색으로 문제$i$를 $T$일부터 $1$일까지 냅색해서 최댓값을 구했다. 어짜피 $N$번 반복문 안에 $T$번 반복문 돌리는거라 그냥 입력할 때 마다 $T$번 냅색했다. 문제를 모두 다 풀었는데도 $T$ 값을 넘지 못하면 제한 일 안에 모든 문제를 풀 수 있으니 벌금은 없다. 아니라면 dp 테이블에서 가장 큰 수를 모든 벌금의 합에서 빼주면 된다. 가장 큰 수를 찾는 이유는 1일 남았을 때 9000, 0일 남았을 때 6000 이런식으로 저장되어 있을 때를 생각해보면 된다.

 

---

H. 땅 자르기 (백준 2175)

다각형의 넓이, 브루트포스

 

먼저 좌표 4개를 받고, 중점을 구한다. 이후 기준점을 다각형의 꼭짓점을 할지, 중점을 할지를 케이스를 나눠서 생각한다.

3개의 점을 이용해서 삼각형의 넓이를 구하고 누적 합해서 반으로 나눠졌을 때 나눠진 다각형의 값을 각각 구할 수 있다. 하나는 전체 넓이에서 지금 구한 다각형의 넓이가 될 것이고, 하나는 구한 다각형의 넓이가 될 것이다. 가장 비슷하게 맞추어야 하니 차의 절댓값이 가장 작은 값이 정답이다.