본문 바로가기

파이썬

 (320)
[Python] 31540번 도박 문제 전문 상담은 국번없이 1336 https://www.acmicpc.net/problem/31540 31540번: 도박 문제 전문 상담은 국번없이 1336 첫 번째 줄에 대회 참가자의 수 $n$, 배당의 총합을 결정할 정수 상수 $m$, $t$가 공백으로 구분되어 주어진다. $(1\le n, m, t\le 10^6)$ 두 번째 줄에 베팅 결과 각 참가자에게 걸린 금액을 나타내는 $n$개 www.acmicpc.net 24/03/10 내가 검수했던 MatKor컵의 한 문제로, 전형적인 수학 문제이다. 두 가지 방법으로 풀 수 있는 좋은 문제이다. 여기서는 의도했던 정해를 중점으로 서브태스크 순으로 따라가며 설명해보고자 한다. 문제 접근 방식: 문제를 요약하면, 준혁이는 도박을 운영하는 도박 운영자고, 사람들에게 받은 돈이 총 $S$원이다...
[Python] 10166번 관중석 https://www.acmicpc.net/problem/10166 10166번: 관중석 KOI 공연장의 관중석에는 가운데에 있는 무대를 중심으로 반지름이 자연수인 동심원(중심이 같은 여러 원들) 위에 다음과 같이 좌석들이 배치되어 있다. 반지름이 1인 원 위에는 좌석이 1개, 반지 www.acmicpc.net 24/02/13 실버 1치고는 많은 고민을 하게 한 문제이다. 각 코드 별로 어떠한 흐름을 가지고 생각했는지 적어보고자 한다. 문제 접근 방식: 처음으로 생각한 것은, 보이는 관중석이 어떤 일정한 규칙을 가지고 있어서, 그 규칙이 수식으로 표현 될 것이라는 생각이 들었다. 그 이후에 바로 보인 사실은, $i < j$일때, 반지름 $i$가 반지름 $j$인 원을 가린다면, 그 가리는 관중석의 개수는 ..
[Python] 2608번 로마 숫자 https://www.acmicpc.net/problem/2608 2608번: 로마 숫자 첫째 줄과 둘째 줄에 하나씩 로마 숫자로 표현된 수가 주어진다. 입력된 각 수는 2000 보다 작거나 같고, 두 수의 합은 4000보다 작다. www.acmicpc.net 24/02/27 단순한 구현 + 문자열 문제이다. 사소한 실수로 두 번 정도 틀렸습니다를 받았다. 문제 접근 방식: 문제에서 요구하고자 하는 것은 로마 숫자로 주어진 두 수를 더하고, 그 결과를 하나는 아라비아 숫자로, 하나는 로마 숫자로 출력하는 것이다. 문제를 읽던 도중 생각난 방법은 아라비아 숫자와 로마 숫자 사이의 일대일 대응 표를 만들어서 각 자리 숫자 별로 매칭을 시키면 충분할 것이라는 방법이었다. 마침 문제 제한을 보았고, 두 수가 모..
[Python] 12445번 バクテリアの増殖 (Small) https://www.acmicpc.net/problem/12445 12445번: バクテリアの増殖 (Small) 微生物の研究者であるパスカルは、特殊な増殖の傾向を示すバクテリアを発見した。どうやらそのバクテリアは、ある時点で x 個存在したとすると、理想的な環境下では1時間後に xx 個に増 www.acmicpc.net 24/02/09 아주 아주 간단한 문제로, 파이썬으로 해결하기에 아주 적절한 문제다. 문제 접근 방식: 이 문제는 Small버전이 존재하고 Large버전이 존재한다. Large버전의 경우, Power tower류의 문제로, 정수론을 배워야 풀 수 있는 문제다. https://www.acmicpc.net/problem/13970 13970번: Power towers In this example, as M =..
[Python] 27114번 조교의 맹연습 https://www.acmicpc.net/problem/27114 27114번: 조교의 맹연습 첫 번째 줄에 각각 좌로 돌아, 우로 돌아, 뒤로 돌아에 들어가는 에너지를 나타내는 세 정수 $A, B, C$와 사용하고자 하는 총 에너지양을 나타내는 정수 $K$가 공백으로 구분되어 주어진다. $(1\leq A,B www.acmicpc.net 24/02/26 간단한 DP문제로, 처음엔 BFS로 잘못 접근했던 문제이다. DP테이블 정의와 점화식 유도는 빠르게 할 수 있었지만, 자잘한 실수가 있어서 아쉬웠다. 문제 접근 방식: $K$만큼의 에너지를 소모하여 처음 바라보고 있던 방향으로 제식 연습을 끝마쳤을 때 제식 수행 횟수의 최솟값을 구하는문제이다. 처음에는 BFS로 접근하고, 과도한 루프 방지를 위해 일정 ..
[Python] 28303번 자석 https://www.acmicpc.net/problem/28303 28303번: 자석 예제 1의 경우 N극이 3번 칸에 놓이고 S극이 5번 칸에 놓이도록 자석을 설치할 때 1번 현상으로 $a_3=22$의 에너지가 충전되며, 2번 현상으로 $a_5=4$의 에너지가 소모되고, 3번 현상으로 $(5-3)\times 2=4$ www.acmicpc.net 24/02/24 누적 합 응용으로, 아이디어를 떠올리니 쉽게 해결할 수 있었던 문제였다. 문제 접근 방식: 문제를 잘 읽고 분석을 해보았다. 배열을 $A$라고 하고, 배열의 $i$번째 원소를 $a_i$라고 한다면, 문제에서 요구하는 것은 $a_i - a_j - |i-j|K$의 값을 최대화시키는 것이다. $N$의 최댓값이 $500,000$이기 때문에, $\mat..
[Python] 18116번 로봇 조립 https://www.acmicpc.net/problem/18116 18116번: 로봇 조립 성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의 www.acmicpc.net 24/02/21 분리 집합 문제로, 집합의 크기를 바로 내보내는 쿼리를 어떻게 구현해야 할 지 집중해야 해결할 수 있는 문제다. 문제 접근 방식: 결론부터 말하면, 집합의 크기를 바로 내보내는 리스트를 따로 관리해주면 된다. 기존 분리 집합 코드에서는 배열의 인덱스는 해당 노드의 값, 배열의 값은 해당 노드를 자식 노드로 가지는 노드의 값, 즉, 부모 노드의 값을 저장한다. 나는 여기에서 집합의 개수..
[Python] 5588번 별자리 찾기 https://www.acmicpc.net/problem/5588 5588번: 별자리 찾기 상근이는 밤하늘 사진에서 별자리를 찾고 있다. 사진에는 꼭 찾고 싶은 별자리와 같은 형태, 방향, 크기의 도형이 한 개가 포함되어 있다. 하지만, 상근이가 가지고 있는 사진 속에는 별자리를 www.acmicpc.net 24/02/01 간단한 브루트포스 문제로, 집합을 사용해 적절히 구현하면 쉽게 해결할 수 있는 문제이다. 문제 접근 방식: 별자리를 구성하는 별들은 리스트로 받고, 사진 속 별 들의 위치는 집합에 넣어주었다. 이후 사진 속의 모든 별들 마다 그 별이 옮겨진 별자리의 중심이 된다고 가정하고 이동량을 구해주었다. 옮기기 전 별자리에 있는 모든 별 마다 그 이동량을 적용해 주었다. 즉, 옮겨진 별의 좌표를..

티스토리툴바