목록알고리즘 (5)
layered
https://www.acmicpc.net/problem/27893 27893번: 특별한 드롭킥 NLCS Jeju의 구조는 생각보다 부실해서, 벽이나 문 등을 드롭킥으로 부술 수 있다. NLCS Jeju의 복도는 1차원 수직선으로 모델링할 수 있으며, 동호의 현재 좌표는 $x=0$이다. 동호는 $x=N$에 있는 교실로 www.acmicpc.net 조금 까다로웠던 문제. 맞왜틀 어떻게 풀어야 할지는 생각했는데, 그게 코드를 구현하는 관점에서는 조잡한 풀이여서 오래 걸린 것 같다. 다 풀고 나서 다른 코드들을 보니 확실히 그런 생각이 들었다. 그럼 시작! 동호가 장애물을 놓는 경우는 크게 두 가지로 나눌 수 있다. 1. 장애물 옆에 놓는다 ..XX.. 2. 장애물만 덩그러니 놓는다. ..X...X 조금 더 ..
https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 기본적인 흐름은 철로를 움직이면서 해당되는 경로(집-사무실)의 개수를 세는 것이다. 이때 관건이 되는 부분은 두 가지라고 생각했다. 1 철로를 어떻게 움직일 것인가? 한 칸씩 움직일 필요는 없다. 부담스럽기도 하고, 어떤 구간은 경로가 위치하지 않을 수도 있어 낭비되는 구간이 생긴다. 최대한 철로의 시작이나 끝부터 경로가 바로 포함되도록 하는 게..
https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 그냥 시뮬레이션 해서 구현하는 문제. 공이 네 방향으로 굴러갈 수 있으므로 bfs 기반이지만 공이 굴러가다가 알아서 방향을 트는 건 불가능하니까 약간의 처리를 해 주어야 한다. 처음 구상은 이랬다. 1 먼저 공이 굴러갈 방향을 찾는다(벽만 없다면 굴러갈 수 있다) 2 공을 가상으로 굴린다 공은 한 번 굴리면 그 방향으로만 쭉 가야 하니까, 차라리 ..
https://www.acmicpc.net/problem/27447 27447번: 주문은 토기입니까? 첫 번째 줄에는 손님의 수를 나타내는 정수 $N$과 토기에 담겨진 커피가 흙탕물이 되는 시간을 나타내는 정수 $M$이 공백을 사이에 두고 주어진다. ($1\le N,M\le 1\, 000\, 000$) 두 번째 줄에는 각 손님 www.acmicpc.net 한별이는 매시간마다 다음 중 하나의 일을 할 수 있다. 1. 토기를 만든다 2. 커피를 담는다 3. 서빙한다 이 일들은 시간과 횟수의 두 가지 관점에서 볼 수 있는데 1. 토기는 언제든 만들어도 되고 남아도 상관이 없다 2. 커피는 너무 일찍 담으면 흙탕물이 되므로 제한된 시간 내에 만들어야 한다 3. 서빙은 손님이 방문한 시간에 해야 하므로 고정되어 ..
블로그 글 옮기는 중.. https://www.acmicpc.net/problem/27740 27740번: 시프트 연산 $0$과 $1$로 이루어진 길이 $N$의 수열 $A_1,A_2,\cdots,A_N$이 주어진다. 주어진 수열에는 다음과 같이 정의된 두 가지 연산을 원하는 대로 적용할 수 있다. L-시프트: 수열의 원소를 한 자리씩 앞으로 옮 www.acmicpc.net 처음에는 그냥 가볍게 생각해서 세 가지 경우가 나왔다. 양쪽 끝이 1인 경우, 0인 경우, 다른 경우. 다음은 그때 작성했던 코드인데 나도 알아보기가 힘드므로 그냥 대충 넘기면 된다. #include #include #include #include #include #include #include #include using namespa..