DP (57) 썸네일형 리스트형 [Python] 1670번 정상 회담 2 / 17268번 미팅의 저주 https://www.acmicpc.net/problem/1670 1670번: 정상 회담 2 첫째 줄에 정상 회담에 참가한 사람의 수 N이 주어진다. 이 값은 10,000보다 작거나 같은 짝수이다. www.acmicpc.net https://www.acmicpc.net/problem/17268 17268번: 미팅의 저주 인하대 컴퓨터 공학과에 재학 중인 이산이는 오랜만에 미팅을 나가 볼까 한다. 미팅은 N명이 원탁에 앉아서 진행된다고 한다. 질투가 난 이산이 친구 명기는 X의 저주를 걸었다. 그 저주는 N명이 www.acmicpc.net 23/12/06 카탈란 수 문제다. 두 문제는 완전히 동일한 문제이기 때문에 같이 올린다. 문제 접근 방식: 예제 출력 보고 카탈란 수 임을 인지한 뒤, 카탈란 수를 출.. [Python] 4099번 Skyline https://www.acmicpc.net/problem/4099 4099번: Skyline There will be several test cases in the input. Each test case will consist of a single line containing a single integer N (3 ≤ N ≤ 1,000), which represents the number of skyscrapers. The heights of the skyscrapers are assumed to be 1, 2, 3, …, N. The www.acmicpc.net 23/12/06 카탈란 수 임을 파악하면 쉽게 해결할 수 있는 문제이다. 문제 접근 방식: 먼저 문제의 입출력 예시를 보자. 어? $3$일때 .. [Python] 28346번 XOR Necklace https://www.acmicpc.net/problem/28346 28346번: XOR Necklace Frograms, Inc. has been busy developing necklaces with brand-new design and feature. Every programmer working at Frograms now wears this necklace. A necklace consists of multiple beads stringed by a thread, as seen below. Each bead is given a number betwee www.acmicpc.net 23/11/28 비트 연산의 성질을 이용한 애드혹 문제이다. 다른 방법으로는 제한 시간이 널널하기 때문에 3차원 DP로.. [Python] 30519번 짜고 치는 가위바위보 (Large) https://www.acmicpc.net/problem/30519 30519번: 짜고 치는 가위바위보 (Large) 가위바위보 챔피언십이 열렸다. 수많은 관중이 지켜보고 있다. 이 상황에서 lighter와 smallant는 가위바위보 챔피언십 결승에 도달했다. 하지만 둘은 어릴 적부터 너무 친한 친구라, 누가 이기든 별 www.acmicpc.net 23/11/05 내가 제작한 문제다. Small버전에 대한 해설은 아래 링크에 있으니 궁금하다면 확인해 보자. 2023.11.25 - [알고리즘/백준 문제 풀이] - [Python] 30518번 짜고 치는 가위바위보 (Small) 문제 접근 방식: 문제 제한을 주목해 보자. 이전 문제는 제한이 $N = 20$이었던 반면, 이 문제의 경우 $N = 1,000,.. [Python] 13255번 동전 뒤집기 https://www.acmicpc.net/problem/13255 13255번: 동전 뒤집기 첫째 줄에 동전의 개수 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 K (1 ≤ K ≤ 50)이 주어진다. 셋째 줄에는 A[i] (1 ≤ A[i] ≤ N)가 주어진다. www.acmicpc.net 23/08/23 최근 확률 DP 문제를 계속 공부하고 있다. 이 문제 또한 확률 DP 문제로 쉽게 해결할 수 있다. 또한, 약간의 최적화를 거치면 매우 빠르게 문제를 해결할 수 있다. 첫번째 접근 방식: 첫 번째로 접근한 방식은 나이브한 $3$차원 확률 DP이다. DP테이블은 다음과 같이 정의했다. $$DP[i][j][k] = i번째 \ 뒤집는 \ 행위를 \ 수행했을 \ 때 \ j번째 \ 동전이 \ k번 .. [Python] 12046번 Not So Random (Small) / 12047번 Not So Random (Large) https://www.acmicpc.net/problem/12046 12046번: Not So Random (Small) The first line of the input gives the number of test cases, T. T test cases follow; each consists of one line with six integers N, X, K, A, B, and C. Respectively, these denote the number of machines, the initial input, the fixed number with which www.acmicpc.net https://www.acmicpc.net/problem/12047 12047번: Not So Random (Large.. [Python] 7670번 Game Dice https://www.acmicpc.net/problem/7670 7670번: Game Dice In the game of Dungeons & Dragons, players often roll multi-sided dice to generate random numbers which determine the outcome of actions in the game. These dice come in various flavors and shapes, ranging from a 4-sided tetrahedron to a 20-sided isocahedro www.acmicpc.net 23/08/21 최근 확률 DP문제를 계속 공부하고 있다. 복습하고자 글로 남긴다. 문제 접근 방식: DP로 접근했으며, DP테.. [Python] 1344번 축구 https://www.acmicpc.net/problem/1344 1344번: 축구 홍준이는 축구 경기를 보고 있다. 그러다가 홍준이는 역시 두 팀 중 적어도 한 팀이 골을 소수로 득점할 확률이 궁금해 졌다. 축구 경기는 90분동안 이루어지고, 분석을 쉽게하기 위해서 경기를 5 www.acmicpc.net 23/08/21 또 다른 확률 DP문제이다. 복습해 보고자 글을 작성한다. 첫 번째 접근 방식: 첫 번째 접근 방식은 확률 DP이다. 나는 다음과 같이 DP테이블을 정의하였다. $$DP[i][j][k] = i번째 \ 구간에서 \ j번째 \ 팀이 \ k점이 \ 될 \ 확률$$ 팀은 $2$팀 밖에 없고, 각 팀이 점수를 얻는 데에는 서로가 서로에게 간섭하지 않으므로, 우리는 한 팀에 대해서만 생각해도 충분.. 이전 1 2 3 4 5 6 7 8 다음
