https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 간단한 시뮬레이션 문제이다. 나는 생각을 어렵게 해서 쌩 배열로 구현해서 그런지 구현이 빡셌지만.. 난이도 매기는 사람들 의견보니 구현은 쉬운편이라고.. 그냥 덱 자료구조로 하면 더 쉽게 할 수 있을 것 같다. Python 리스트 (배열) 사용 풀이 배열과 리스트는 다르지만 사실상 리스트를 배열처럼 활용하여 풀었다. 나는 2N 개의 배열을 미리 잡아두고 '올리는 위치(put_..
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/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 시뮬레이션, 구현, 브루트포스 유형의 문제이다. 생각보다 구현이 빡빡하다. (체감 난이도 골드4) 이 문제를 풀 때 내가 실수했던 부분은 하나였다. 감시구역이 겹치는 점을 고려하지 못한 것이다. 그래서 백트래킹으로 감시구역을 바꿀때, 다른 CCTV에 의해서도 감시되는 구역에 대해 감시를 풀어버린 것 때문에 틀렸었다. 그래서 숫자를 이용해 감시 카운트를 세도록 했다. 감시가 생길때마다 숫..
https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 스티커 문제를 발전 시킨다면 이 파이프 옮기기 문제가 될 것 같다. 좋은 DP 연습문제이다. 처음에는 당연히 BFS를 이용해서 풀어야겠다고 생각했는데, BFS로는 최단경로를 찾아보기만 했지, 최단경로의 '개수'를 세어보진 않아서 백준님의 표현을 빌리자면, BFS의 형태를 모방한 브루트포스 풀이로 밖에 짜지지가 않았다. (그리고 이 방식은 당연하게도 시간초과를 받는다..) ..
