본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 25793번 초콜릿 피라미드 https://www.acmicpc.net/problem/25793 25793번: 초콜릿 피라미드 코코는 특이하게 생긴 화이트 초콜릿과 다크 초콜릿을 무한히 많이 갖고 있다. 화이트 초콜릿은 각 모서리의 길이가 1인 사각 피라미드이고, 다크 초콜릿은 각 모서리의 길이가 1인 정사면체 모 www.acmicpc.net 22/10/15 전형적인 수학 문제로, $O(1)$의 시간 복잡도로 문제를 해결해야 풀 수 있다. 문제 접근 방식: 아래 그림을 보자. 아래 그림은, $2*3$ 피라미드의 한 층을 채우는 과정을 도식화한 것이다. 이 그림을 이용해, 예시를 하나 들어보겠다. 만약 $R = 3$, $C = 4$라면, 다음 그림과 같은 모습을 띄게 될 것이다. 이 그림은 $3*4$ 피라미드의 한 층을 채우는 데에 ..
[Python] 5011번 Robots on a grid https://www.acmicpc.net/problem/5011 5011번: Robots on a grid You have recently made a grid traversing robot that can find its way from the top left corner of a grid to the bottom right corner. However, you had forgotten all your AI programming skills, so you only programmed your robot to go rightwards and downwards www.acmicpc.net 22/10/14 전형적인 BFS문제에 갈 수 있는 방법을 구하는 DP문제가 더해진 문제로, 개인적으로 골드 5가 적당..
[Python] 16958번 텔레포트 https://www.acmicpc.net/problem/16958 16958번: 텔레포트 2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔 www.acmicpc.net 22/10/27 다양한 풀이가 존재하는 문제로, 파이썬으로 풀기 위해서는 별의별 최적화를 다 해야 되는 문제이다. 나이브한 플로이드-워셜 알고리즘으로 접근한다면 파이썬에서는 TLE를 받을 수밖에 없기 때문에 무조건적인 최적화가 필요하다. 이 글에서는 2가지 풀이 방법을 소개할 것이다. 첫 번째 문제 접근 방식: 이 문제를 먼저 접했을 때, 도시의 수의 ..
[Python] 11869번 님블 https://www.acmicpc.net/problem/11869 11869번: 님블 님블은 1×N 직사각형에서 즐기는 게임이다. 직사각형은 1×1 크기의 정사각형으로 나누어져 있고, 가장 왼쪽 정사각형은 0번, 그 오른쪽 정사각형은 1번, ..., 가장 오른쪽 정사각형은 N-1번이다. 각 www.acmicpc.net 22/10/13 그냥 다른 게임을 가장한 nim게임으로, nim게임 풀듯이 풀면 된다. 문제 접근 방식: 그냥 모든 숫자들을 xor 하면 끝이다. 아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다. 더보기 # 11869번 님블 # 게임이론, 스프라그-그런디 정리 ''' 그냥 nim게임임 ''' N = int(input()) total = 0 nu..
[Python] 16899번 채석장 게임 https://www.acmicpc.net/problem/16899 16899번: 채석장 게임 첫째 줄에 채석장의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 채석장의 정보가 주어진다. 채석장의 정보는 두 정수 Xi, Mi (1 ≤ Xi, Mi ≤ 1016)로 이루어져 있다. www.acmicpc.net 22/10/13 전형적인 nim게임으로, 그냥 XOR을 하면 시간 초과가 나는 문제이다. XOR연산의 성질을 이용해야 풀 수 있는 영리한 문제이다. 문제 접근 방식: 문제의 조건을 자세히 살펴보면, N의 크기가 최대 10만이고, Mi가 최대 10의 16승까지 있으므로, 그냥 모든 숫자들을 XOR 연산시키려고 한다면 무조건 시간 초과가 난다. https://www.acmicp..
[Python] 25591번 푸앙이와 종윤이 https://www.acmicpc.net/problem/25591 25591번: 푸앙이와 종윤이 베다수학 곱셈법을 쓰는 과정에서 구하는 $a$, $b$, $c$, $d$, $q$, $r$을 첫 줄에 공백으로 구분해서 출력한다. 둘째 줄에 곱셈 결과의 앞의 두 자릿수, 뒤의 두 자릿수를 공백으로 구분해서 출력한다. www.acmicpc.net 22/10/12 그냥 주어진 문제를 그대로 구현하면 되는 문제이다. 문제 접근 방식: 문제 잘 읽고 풀면 된다. 전형적인 문제 읽기가 힘든 문제. 아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다. 더보기 # 25591번 푸앙이와 종윤이 m, n = map(int, input().split()) a = 100 - m b =..
[Python] 17114번 하이퍼 토마토 https://www.acmicpc.net/problem/17114 17114번: 하이퍼 토마토 첫 줄에는 문제의 설명에서 창고의 크기를 나타내는 자연수 m, n, o, p, q, r, s, t, u, v, w가 주어진다. 단, 1 ≤ mnopqrstuvw ≤ 106 이다. 둘째 줄부터는 창고에 저장된 토마토들의 정보가 주어진다. 창 www.acmicpc.net 22/10/11 기존 토마토 문제(7576번, 7569번)와 기본적인 접근 방법 자체는 똑같다. 하지만, 11차원으로 인해 생기는 시간 부족을 관리해야 되기 때문에 약간 코드가 다르게 적을 수밖에 없었다. 2022.09.20 - [백준 문제 풀이] - [Python] 7576번 토마토 [Python] 7576번 토마토 7576번: 토마토 (acm..
[Python] 1205번 등수 구하기 https://www.acmicpc.net/problem/1205 1205번: 등수 구하기 첫째 줄에 N, 태수의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000보 www.acmicpc.net 22/10/10 단순 구현 문제로, 주어진 상황을 그대로 해석하여 문제를 구현하면 된다. 문제 접근 방식: 먼저 현재 랭킹 리스트에는 몇 명 있는지(N), 태수의 새로운 점수(new_score), 랭킹 리스트에 올라갈 수 있는 점수의 개수(P)가 주어진다. 먼저 경우의 수를 나눌 수 있다. 만약 현재 랭킹 리스트에 아무도 없는 상황이라면, 랭킹 리스트에 올라갈 수 있는..

티스토리툴바