본문 바로가기

파이썬

 (320)
[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$팀 밖에 없고, 각 팀이 점수를 얻는 데에는 서로가 서로에게 간섭하지 않으므로, 우리는 한 팀에 대해서만 생각해도 충분..
[Python] 15488번 나이트가 체스판을 벗어나지 않을 확률 https://www.acmicpc.net/problem/15488 15488번: 나이트가 체스판을 벗어나지 않을 확률 첫째 줄에 N, 나이트의 좌표 x, y, 이동 횟수 K가 주어진다. (1 ≤ N ≤ 50, 1 ≤ x, y ≤ N, 0 ≤ K ≤ 50) www.acmicpc.net 23/08/18 확률DP 문제로, 이 유형을 처음 접해봤기 때문에 복습을 해보고자 글을 작성한다. 첫 번째 접근 방식: 처음 접근 방식은 BFS를 구현하여 직접 나이트를 옮기면서 나올 수 있는 확률들을 모두 곱하는 방식이었다. 이 방식은 다음과 같다. 우리는 나이트가 $K$번 이동한다는 사실을 알고 있고, 나이트가 체스판을 벗어나는 이동을 하는 순간, 그 즉시 더 이상 움직일 수 없다는 것 또한 알고 있다. 기본적인 방법은..
[Python] 25280번 Marathon https://www.acmicpc.net/problem/25280 25280번: Marathon Erik wants to run a marathon. Most of all, he wants to win the race. To plan his training, he has looked up how the other contestants performed in previous races and made a model to predict his chances of winning. The finishing time for each contestant is www.acmicpc.net 23/08/05 확률론적인 부분만 해결하면 쉽게 풀 수 있는 이분탐색 문제이다. 문제 접근 방식: 문제는 그렇게 길지 않으니 바..
[Python] 24838번 배열 구간합 놀이 https://www.acmicpc.net/problem/24838 24838번: 배열 구간합 놀이 각 테스트 케이스의 정답인 Alice가 달성할 수 있는 $S(A, x, y)$의 최댓값, 그리고 이를 달성할 수 있는 방법의 수를 공백으로 구분하여 출력한다. 단, 방법의 수가 매우 커질 수 있으므로 $10^9+7$로 www.acmicpc.net 23/08/04 내가 있는 스터디 그룹에서 이번 주 주간 문제로 다룬 문제 중 하나로, 구간 합을 적절히 이용한 재미있는 문제이다. 단점이라고 하면, 지문이 너무 길다는 것... 이 글에서는 지문을 전부 이해하고 있다는 가정 하에서 글을 쓸 것이다. 문제 접근 방식: 문제에서 주어진 예제를 잘 이해해 보자. 예제에서는 결론적으로, $1000$을 $2$번 더하고, ..
[Python] 24187번 Korta vokaler https://www.acmicpc.net/problem/24187 24187번: Korta vokaler Att lösa algoritmproblem är svårt, men en sak som ofta är ännu svårare är att förbereda testdatan. Ta problemet Arabiska till exempel. Här har juryn lagt många timmars intensivt arbete åt att konstruera mästerverk som hej vad heter du. En fråg www.acmicpc.net 23/07/03 언어 장벽이 있는 스웨덴어 문제로, 다른 사람들의 풀이와는 다르게 푼 듯 하여 올려본다. 문제 접근 방식: 먼저, 문제를 요..
[Python] 24230번 트리 색칠하기 https://www.acmicpc.net/problem/24230 24230번: 트리 색칠하기 정점이 $N$개인 트리가 있다. 정점에는 1부터 $N$까지 번호가 붙어있다. 트리의 루트는 항상 1번 정점이며 맨 처음에는 모든 정점이 하얀색으로 칠해져 있는 상태이다. 하나의 정점에 색칠하면 해 www.acmicpc.net 23/05/29 골드 5 짜리 문제 치고는 아이디어가 매우 좋았던 문제이다. 문제 접근 방식: 문제 정보를 보면, 트리가 주어져 있는데 각 노드별로 색깔 정보가 주어진다고 했다. 한 노드를 색칠하면, 그 노드를 포함한 서브트리는 모두 같은 색으로 색칠된다고 한다. 이때, 모든 정점을 원하는 색으로 칠하고자 할 때 구하는 최소 색칠 횟수를 구하는 것이 우리의 목적이다. 맨 처음 떠올렸던 방..
[Python] 15703번 주사위 쌓기 https://www.acmicpc.net/problem/15703 15703번: 주사위 쌓기 아래 설명에서 k개의 주사위가 쌓여져 있고, 위에서부터 적혀있는 정수가 s1, s2, ..., sk인 주사위 탑을 (s1, s2, ..., sk)로 표현했다. 예제 1의 경우에는 주사위 탑 1개를 만들 수 있다. (1, 2, 4, 5) 또는 ( www.acmicpc.net 23/05/25 구현을 조금 요하는 그리디 문제이다. 문제 접근 방식: 문제 요약을 하면 다음과 같다. 주사위가 주어져 있고, 하나의 주사위의 모든 면에는 같은 눈금이 적혀있다. 이런 주사위들을 모아 주사위 탑을 쌓고자 하는데, 한 주사위에 적힌 눈금이 $5$라면, 그 주사위 위에는 $5$개를 넘어서 주사위를 쌓을 수 없다고 한다. 이럴 때,..

티스토리툴바