저번주 시험주간 내내 거의 풀질못했다... 이번주는 많이 풀어보는걸로
27277 장기자랑 S1
#greedy
n이 10만이기 때문에 dp보단 O(n), O(n log n) 그리디하게 접근해보자.
맨앞에 있는 사람은 무조건 발휘할수 있다. <- 이는 젤 큰 값을 배치하면 될 것.
그렇다면 그 다음 사람은 무조건 할 수 없다. <- 제일 작은 값을 배치하면 됨.
... 이런 방식으로 배열을 정렬 한 다음, 큰값-작은값 순으로 배치하면 O(n log n)만에 풀 수 있다.
여담으로 예제에 나온 내용은 그냥 낚시다.
17182 우주탐사선 G3
#bit dp
외판원순회문제처럼 보이지만, 사뭇 다르다. (다시 출발로 돌아오지 않아도 되고, 이미 갔다온데를 한번더 갈 수도 있다.)
bit dp으로 해결해보자.
dp[cur][visited]: 현재 행성이 cur이고, visited는 지금까지 방문한 행성들의 집합일 때, 시작점에서부터 현재 상태까지의 최소 시간을 비트로 표시 한거라고 정의하자.
현재 상태에서 모든 가능한 다음 행성으로 이동하면서 DP 값을 갱신하자.
모든 행성에서 끝날 수 있으므로, dp 배열의 해당 상태 중 최소값을 찾자.
22479 ConvexCut G1
#geometry
Convexhull과는 아무 상관없는 문제다...
P를 통과하는 어떠한 직선으로 볼록 다각형을 절단해도, 절단 후에 얻어진 2개의 볼록 다각형의 면적이 동일한 점 P의 좌표를 구하라. 는 문제이다.
이 말은 즉슨, 도형이 대칭일 때 그 대칭점의 중심점을 계산해야 되기 때문에, 점의 갯수가 홀수면 불가능하다.
짝수 개의 점들로 이루어진 다각형에서 각 점과 그 대칭점의 중점을 계산한 다음, 그 중 첫 번째 중점을 출력 하면 된다.
24886 SKH 문자열 P5
#greedy
case를 나눠서 생각해보자. greedy하게 SKH가 같이 있으면 그대로 SK, SH, KH가 있다면 1개씩 끼울 수 있을 것이다. S, K, H 따로 있다면, KH, SH, SK를 끼워 만들 수 있을 것이다. 그 외에도 필요한 SKH 1개씩 사용해 독립적으로 SKH를 만들 수 있을 것이다.
예제를 보면 끼워 넣는 과정에서 한개만 다 사용하는 방법이 아닌 밸런스 있게 SKH를 만들어야 한다.
임의의 ) 에 대해서, K에 SH를 붙이고 H에 SK를 붙이고 SKH를 붙이는 나머지 과정을 모든 x에 대해서 수행한다. 나머지 2가지 방법도 동일하게 수행한다.
https://www.acmicpc.net/source/share/3f9f326f740f4e7aa2bdde8c57f3cbb1
1474 밑줄 S1
#greedy #string
우선 밑줄갯수의 차가 1이기 때문에 밑줄의 갯수가 n인 경우, n+1인 갯수를 각각 구해주자.
그런 다음, 밑줄 다음 문자가 소문자인경우, 밑줄이 더 우선순위가앞이기 때문에 밑줄 갯수를 n+1이 되어야 한다. 반대로 대문자일 경우, 대문자가 더 우선순위 앞이기 때문에 밑줄 갯수가 n개 되어야 한다.
추가적으로 무조건 문자열의 길이를 k정확하게 맞춰야 하기 때문에 전부 다 대문자일 경우, 문자열 뒤에 밑줄은 강제로 n+1개를 만들어주자.
15017 Best Relay Team S4
#bruteforce
먼저달릴 1인 + 나중에 달릴 3인으로 최적의 4인을 뽑아야 하는 문제다.
나중에 달릴 기록으로 먼저 sort를 해준 다음, 1,2,3째 + 나중에 달릴 친구가 가장 최적일 것이다.모든 n을 순회해주면서 나중에 달릴친구 + 1,2,3번쨰의 최적조합을 구성해보자.최종 선정된 사람들의 이름도 출력해주어야 하기 때문에 그 사람들의 index도 신경써주면서 구현해주어야 한다. 처음에 permutation으로 구현하였다가 MLE맞았다...http://boj.kr/669edc1bf2564b3498312e87ed4bf4d4
17529 Artwork P5
#dsu #geometry
문제를 정리하자면, 직사각형안에 여러개의 원이 있는데, 왼쪽 하단에서 오른쪽 상단까지 원을 피하는 것이 가능한가?를 묻는 문제이다.
그렇다면 이 원들이 막고 있느냐?를 판단해야 하는데, 각 벽 역시 하나의 componet라고 가정하고, 원하고 벽하고 교차가 된다면, union해주자.
최종적으로 왼쪽 벽이랑 오른쪽 벽의 parent가 같은가? 위아래 벽의 parent가 같은가? 왼쪽벽과 아래 벽의 parent가 같으냐?로 벽의 막힘유무를 체크해주었다.
추가 반례로 애초에 원이 (0,0) (n,m)을 가리면 그냥 안되는 case이다. 이거 떄문에 맞왜틀을 엄청많이하였다...
이 링크에 해설에 있는 figure가 좀 더 명확할 것 같다.
'ps > Solved' 카테고리의 다른 글
| 11월 3째주 PS정리 (0) | 2024.11.11 |
|---|---|
| 11월 2째주 PS 정리 (0) | 2024.11.04 |
| 10월 4째주 PS정리 (0) | 2024.10.22 |
| 10월 3째주 PS 정리 (1) | 2024.10.14 |
| 10월 2째주 PS 정리 (0) | 2024.10.07 |