코딩스토리

www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 연구소 문제는 매우 유명한? 문제이기 때문에 한번 풀어보았다. 문제를 읽어보면 알겠지만 연구소 1과 비슷하게 백트래킹과 bfs를 사용하여 해결하면 될 것 같았다. 가장 걱정되었던 것은 시간제한이 0.25초인 거였지만 아무리 봐도 다른 풀이가 떠오르지 않아서 생각한 대로 구현해보았다. 풀이과정은 다음과 같았다. 1) 바이러스를 놓을 수 있는 모든 위치를 찾아놓음(최대 10개) 2) 모든 경우를 계산함 3) 이때 각 위치에..

백준 17144번 - 미세먼지 안녕! https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 이 문제는 시뮬레이션 문제이다. 문제의 정답률이 높길래 쉬울 거라 생각했는데 생각보다 오래 걸렸다. 문제를 풀면서 가장 기억에 남는 실수 두 가지는 1. 확산은 동시에 된다. 2. 바람이 부는 것을 구현할 때 끝에서부터? 시작해야 한다. 쉽게 말하면 아래의 코드는 왼쪽에서 오른쪽으로 바람이 부는 코드인데, 왼쪽부터 시작하지 않고 오른쪽 끝부터 시작한다. 1 ..

백준 16235번 - 나무 재테크 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 이 문제는 구현 문제인 것 같다. 처음에 문제를 읽고, 봄, 여름, 가을, 겨울을 각각 함수로 만들고 deque와 tuple을 사용해 코드를 짜 보았는데 당연히 시간초과.. 이유는 아마 deque를 사용하고 체크하는 과정에서 tuple을 사용하면 deque의 장점인 인덱스 접근의 의미가 사라진다. (tuple은 index로 접근이 불가.. tie ..

백준 16236번 - 아기 상어 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 아기 상어 문제는 bfs알고리즘으로 해결하였다. 처음에는 전형적인 bfs문제라 생각하고 문제의 조건 중 가장 가까운 거리에 있는 물고기가 많은 경우의 조건을 잘못 생각해서 bfs를 북 서 동 남 순서대로 돌리면 알아서 조건을 만족할 거라 생각했다. 예제를 돌려보다 이런 방식은 오류가 난다는 것을 알 수 있었다. vector에 pair로 저장해서 가장 가까..

백준 14503번 - 로봇 청소기 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 이 문제는 시뮬레이션 문제이다. 처음 문제를 봤을 때 "왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다." 이 문장을 보고 해당 칸의 왼쪽 방향에 있는 모든 칸들을 확인해야 하는 문제로 착각했다. (솔직히 문제가 오해의 소지가 있게 보이긴 했음ㅠ) 그렇게 해서 함수로 전부 확인하고 예제를 돌려보니 ..