23305 수강변경 S4
#greedy, #hash
n<=1000000 이기 때문에 o(n)으로 풀수있는 방법을 생각해보자.
교환이 무한정 가능하기 때문에 dictonary으로 해당 요구하는 문자열이 있는지 매번 체크해주자.
아이디어 구현이 까다로웠던 문제.
2487 섞기수열 G4
#math, #graph
문제 자체는 순열을 Cycle Decomposition 했을 때, 가장 긴 length를 구하는 문제일거라 생각했다.
예제를 유심히 관찰해보자. 예제를 decomposition 해보면 3, 1, 2가 나오는데 답이 6이다.
답은 모든 length의 최대공배수를 구하면 된다. 예제에서 많은 힌트를 얻었다.
추가로 cycle의 갯수가 1개, 2개일때 예외처리를 잘해주자.
14302 Codejamon Cipher (Small) G5
#dp
각 쿼리 별 모든 문자열로 만들수 있는 경우의수를 구하는 문제이다.
각 단어는 무작위로 배치할 수 있으니 dictonary활용하여 a몇개, b몇개...z가 몇개 포함되어있는지 체크해주자.
dp[j]은 dp[0:j] 까지 만들수 있는 문자열의 경우의수로 정의해보자.
dp[j+1]=(dp[j+1]+dp[j−k]× 부분 문자열의 개수) mod MOD 으로 점화식을 세울 수 있다.
14303 Codejamon Cipher (Large) G4
#14302와 동일
9134 Komunikace G1
#graph, #dsu
3차원 공간을 graph으로 변환해 MST를 만드는 cost를 구하는 문제
무엇보다 구현과 input이 많이 이상하다...
코드가 너무 더럽다.... 시간이 있다면 수정해서 올릴 것.
9169 나는 9999번 문제를 풀 수 있다 P2
#flow
전형적인 Flow Min cut 문제
이분 그래프를 모델링 할 때, source -> 맞출수있다 -> 맞출수없다 -> sink 으로 모델링 가능하다
이렇게 모델링 돌려주고 edmonds karp 사용해서 답을 구하자.
14686 Sum Game B2
#prefix sum
배열 2개를 누적합 해주면서 값이 겹치는 경우를 매번 update해주면 된다.
18419 桁和 (Digit Sum) S1
#dp
n까지 도달하는데, 몇가지의 방법이 필요한가?를 묻는 문제
dp[n]을 n으로 만들수 있는 가짓수라고 가정했을때,
모든 자리수의 분해합을 i라고 정의했을때 dp[n]은 매번 dp[i] + 1로 update 할 수 있다.
먼가 말로 설명하면 어렵다... 코드보면 쉽게 이해할수있을 듯
19071 Build the Graph G3
#adhoc, #graph #greedy
입력범위가 매우 크기 때문에 o(1)로 푸는 방법을 생각해보자.
연결할 수 있는 최대 edge보다 m이 크다면, 모두다 연결 가능 할 것이다.
그렇지 않다면, 최대한 greedy하게 연결해야 하는데, 1번 node와 그 외 node를 먼저 다 연결하자.
그 다음은 어떻게 연결해야 최적으로 연결하는건지 생각해보자.
9019 DSLR G3
#bfs
BFS로 digit를 만드는 연산을 추적하면 되는 문제
문자열 + 연산으로 명령어를 append한다면 TLE난다. (+연산이 매우느림)
따라서, 구할 수 있는 연산들을 다 찾은 뒤, 마지막에 합치는 방식으로 최적화 해보자.
본 난이도보단 어려웠던 문제.
1017 소수쌍 P3
#flow #bipartite_matching
소수는 홀수이고, 홀수 + 짝수 = 홀수 인 성질을 이용해 이분매칭을 하기 위한 이분 그래프의 설계를 홀수집합, 짝수집합으로 나눌 수 있다.
이후, 첫번째 원소와 매칭시켜줘야하기 때문에 첫번째 원소가 소속되어 있는 원소집합을 고정해놓자.첫번째 원소가 홀수인지 짝수인지에 따라 그룹의 위치를 지정하고, 반대 집합 각 원소별 첫번쨰 원소와, 후보 원소를 지운 다음, 전부 매칭이 되는지 확인하자.http://boj.kr/ee999fee1ab440aaa409fe92cc8b4e40
'ps > Solved' 카테고리의 다른 글
| 10월 4째주 PS정리 (0) | 2024.10.22 |
|---|---|
| 10월 3째주 PS 정리 (1) | 2024.10.14 |
| 10월 2째주 PS 정리 (0) | 2024.10.07 |
| 10월 1째주 PS 정리 (0) | 2024.09.30 |
| 9월 4째주 PS정리 (2) | 2024.09.24 |