https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 간단한 시뮬레이션 문제이다. 나는 생각을 어렵게 해서 쌩 배열로 구현해서 그런지 구현이 빡셌지만.. 난이도 매기는 사람들 의견보니 구현은 쉬운편이라고.. 그냥 덱 자료구조로 하면 더 쉽게 할 수 있을 것 같다. Python 리스트 (배열) 사용 풀이 배열과 리스트는 다르지만 사실상 리스트를 배열처럼 활용하여 풀었다. 나는 2N 개의 배열을 미리 잡아두고 '올리는 위치(put_..
https://www.acmicpc.net/problem/3653 3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net 세그먼트 트리 연습 문제로 풀게 된 문제 1시간을 고민해도 아이디어가 전혀 안 떠올라서 블로그 3~4개 풀이를 다 읽어보고 겨우 이해했다. 그리고 구현하는데 또 시간초과 나서 구현 디테일 수정하느라 30분은 또 쓴 것 같다. 영화를 볼 때마다 꺼낸 영화보다 위에 있던 영화들의 위치가 한칸씩 밀리는 것이 이 문제의 어려운 점이다. 이는 N+M개의 리프노드를 가지는 세그트리를 구현하여 해결할 ..
https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 학교 동아리 스터디에서 세그트리 연습문제로 나와 풀게 되었다. 스터디 수업때 다뤘던 연습문제와 세그트리를 적용하는 결이 달라 한참 고민을 하고 풀었다. 보통 '세그먼트 트리' 하면 유명한 연습문제가 '구간 합 구하기' 이다. https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,0..
https://www.acmicpc.net/problem/27172 27172번: 수 나누기 게임 《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다. 《수 나누기 게임》의 규칙은 다음과 같습니다. www.acmicpc.net 에라토스테네스의 체를 구하는 과정을 응용하여 푸는 문제이다. 수가 10만개 이므로, 임의 두 수의 쌍을 모두 구해서 대결을 시키는 것은 시간내에 풀 수 없다. 1. 미리 1부터 100만까지 모든 수에 대한 점수를 저장할 리스트를 만들어 두고, None으로 초기화를 시켜둔다. (점수가 음수가 될 수 있기 때문이다) 2. 플레이어가 가진 수로 주어진 모든 수에 대해 점수를 0으로 설정한다. 3. 각 플레이어..
https://www.acmicpc.net/problem/30105 30105번: 아즈버의 이빨 자국 집안의 먹을 것들이 계속해서 사라지는 당신은 이웃집의 곰 아즈버(azber)를 의심하고 있다. 오늘, 당신은 드디어 결정적인 증거를 찾아냈는데, 그것은 바로 쵸코바에 찍힌 이빨 자국이었다! 당신 www.acmicpc.net 처음 문제를 읽었을 때는 감이 안왔는데, 시간 제한을 보고 브루트포스라는 감을 잡아 풀었다. N의 사이즈가 4000개이므로, 임의 2개의 점 사이 모든 간격을 구하는데 1.6 * 10^7 의 연산이 필요하고, 이는 3초안에 충분히 가능한 연산이다. 나는 임의 두점 x1, x2 사이의 거리를 구하고, 해시맵에 그 거리를 key 로 하여 그 거리를 구성한 점들을 set으로 저장했다. Ma..
https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 추의 개수와 각 추의 무게가 주어졌을 때, 주어진 추들을 양팔 저울에 올려 측정할 수 있는 무게의 종류를 구하는 문제이다. 추를 양팔 저울의 한 쪽에만 올리는 경우와 다른 반대쪽에도 올릴 수 있는 경우가 있다는 점이 이 문제의 어려운 점이다. 측정하려는 무게를 x, 현재 사용하는 추의 무게를 w, 이전까지 측정한 적 있던 무게를 p 라고 하자. 그렇다면 측정하려는 무게를 양팔저울의 왼쪽에 놓았을 때..
https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 한 노드에 대한 최단 경로에 특정 경로가 포함되어 있는지를 확인하는 문제이다. 아이디어는 어렵지 않은데, 구현이 복잡하다. 나는 처음에 다익스트라를 한번 돌리면서, 그 과정에 간선이 포함되는지를 체크하려고 하였다. 그런데 최단경로가 여러개인 경우, 간선이 포함된 최단 경로를 먼저 고르는 것을 구현하기가 어려워서 이 방법은 포기했다. (나중에 난이도 기여 내역을 보니 이렇게 푼 사람도 있었다...
https://www.acmicpc.net/problem/28458 28458번: Mahjong Tenpai 3통을 가져왔을 경우 3삭 2개를 머리로 사용한 후 3삭 4삭 5삭의 슌쯔를 몸통1, 3삭 4삭 5삭의 슌쯔를 몸통3, 1통 2통 3통의 슌쯔를 몸통3, 3통 3통 3통의 커쯔를 몸통4로 볼 수 있다. 6삭을 가져왔을 경 www.acmicpc.net 주어진 마작패가 대기패인지 아닌지 판별하고 대기패라면 완성패가 되기 위해 추가해야 하는 패를 출력하는 문제이다. 일단 대기패의 구성 숫자가 13장이고, 완성패의 구성숫자가 14장으로 크지 않고 패의 종류도 많지 않아서 브루트포스를 돌리면 되겠다고 생각했다. 그래서 34종류의 모든 패를 하나씩 대기패에 추가해보고 그렇게 구성한 패가 완성패인지 아닌지 판..
https://www.acmicpc.net/problem/28457 28457번: Every? Only One's Marble 첫 번째 줄에는 보드의 크기 $n$, 시작 시 가지는 돈 $S$, 시작점을 지나면 받게 되는 월급 $W$, 황금 열쇠 카드의 개수 $G$가 주어진다. ($3\leq n\leq 10$, $1\leq G\leq 4n-8$, $1\leq S,W\leq 10^7$) 그다음 $G$개의 www.acmicpc.net 부루마블 게임을 구현하는 문제다. 그래도 플레이어가 1명이라 구현 난이도가 엄청 높진 않다. (플레이어가 여러명인 Yut Nori 같은 문제 구현에 비하면..) 구현할 때 다음과 같은 2가지 사항에 주의해야했다. 1. 보드의 사이즈가 작을 때는 주사위 한번으로 2바퀴를 돌 수도 ..
https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 개인적으로 플레 난이도 치고는 풀만한 문제라고 생각한다. 중복되는 키가 연속으로 들어오는 경우를 체크하는게 고민 포인트. 내가 푼 알고리즘은 다음과 같다. 0. 맨 처음에 들어오는 키는 그냥 스택에 넣는다. 1. 수를 입력받으면 해당 수와 스택의 탑에 있는 값을 비교한다. 1.1 탑에 있는 값 > 새로 들어온 값 인 경우 (키가 감소) 탑에 있는 값과 새로 들어온 값이 서로..
