문제 이해 단계 https://www.acmicpc.net/problem/14925 14925번: 목장 건설하기 랜드 씨는 퇴직금으로 땅을 사서 목장을 지으려 한다. 그가 사려고 소개받은 땅은 직사각형이고 대부분 들판이지만, 여기저기에 베기 어려운 나무와 치울 수 없는 바위가 있다. 그는 목장을 하 www.acmicpc.net MxN 맵에 장애물이 있다. 장애물은 1과 2로 나타난다. 이때 정사각형을 최대한 크게 만들 때, 정사각형 변의 길이 L의 길이를 구하는 문제 문제 접근 단계 문제는 굉장히 직관적이다. 제한사항부터 바로 살펴보면 N과 M의 최대 길이가 5000인 상황. 5000 x 5000 = 25,000,000까지 가능하다. 브루트 포스는 힘들어 보인다. 만들어야 하는 것은 2차원 맵이 주어지기..
문제 이해 단계 https://www.acmicpc.net/problem/22871 22871번: 징검다리 건너기 (large) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net N개의 돌이 일렬로 나열되어 있고 목표는 가장 왼쪽 돌에서 가장 오른쪽 돈으로 이동하는 것이다.이동하는 데에는 아래 3가지 조건이 따른다. 1. 무조건 왼쪽에서 오른쪽으로만 움직일 수 있다. 2. i번째 돌에서 j번째 돌로 이동할 때 드는 힘 K는 ( j - i ) * ( 1 + (A_i) - |A_j| )이다. 3. 돌..
문제 이해 단계 https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net NxM맵에 적이 배치되어 있다. 그리고 궁수는 무조건 NxM 맵 밖에 있는 N+1 위치에 3명만 존재한다. N+1 위치는 성의 위치이기도 하다. 하나의 칸에는 무조건 한 명이 궁수만 존재할 수 있다. 궁수는 사거리가 D 이하인 적들만 없앨 수 있다. 궁수 3명은 무조건 동시에 공격을 하며, 같은 적을 공격할 수도 있다. 공격당한 적은 게임에서 제외된다. 적을 선정하는 기준은 궁수에게 거리가 ..
문제 이해 단계 https://www.acmicpc.net/problem/16235 NxN 크기에 땅에 M개의 나무를 심는다. 나무에는 (x, y) 좌표 정보와 나이가 정보가 존재한다. 그리고 2차원 맵에 각각의 칸에는 양분이라는 정보들이 존재한다. 결과적으로 구해야 하는 것은 K 년 이후에 살아있는 나무의 개수인데, 1년은 4계절로 이루어져 있다. 그리고 계절마다 수행해야 하는 기능들이 존재한다. 봄 - 나무가 자신의 나이만큼 양분을 먹는다. 여러 개일 경우 나이가 작은 순으로 먼저 먹는다. - 자신의 나이만큼 양분을 먹지 못할 경우, 양분을 먹지 않고 죽는다. 여름 - 봄에 죽은 나무들의 나이 절반이 - 해당 칸의 양분으로 들어간다. 가을 - 칸에 있는 나무가 5의 배수일 경우 - 인접한 8개의 칸에..
문제 이해 단계 https://www.acmicpc.net/problem/16236 NxN 크기 맵에 상어와 물고기가 존재한다. 물고기와 상어는 각각 한 칸씩만 차지한다. 상어에는 크기, 물고기를 먹은 수의 개수 정보가 존재한다. 그리고 상어가 이동할 때는 아래의 규칙을 따른다. 1. 상어보다 크기가 작은 물고기만 먹을 수 있다. 2. 상어에게 제일 가까이 있는 물고기를 먹는다. 2-1 여러 마리가 있다면 가장 위쪽, 가장 위쪽이 여러 마리라면 가장 왼쪽 물고기를 먹는다. 3. 상어는 자신보다 큰 물고기가 있는 칸은 지나갈 수 없다. (0인 칸이나, 크기가 같은 물고기가 있는 칸은 지나갈 수 있다.) 그리고 상어가 물고기를 먹으면 생기는 일은 아래와 같다. 1. 물고기를 먹은 수가 상어의 크기와 같아지면..
문제 이해 단계 https://www.acmicpc.net/problem/17140 3x3 배열로 시작해서 R연산과 C연산 2가지 연산이 존재한다. 이 2가지 연산 중 한 가지 연산으로 최대 100초까지 반복한다. 행이 더 많거나 같으면 R연산, 그렇지 않으면 C연산을 한다. R연산은 같은 행에 있는 숫자들을 (숫자, 그 숫자의 개수) 쌍으로 정리해서 나타낸다. C연산은 같은 열에 있는 숫자들을 저런 쌍을 정리해서 나타낸다. 이런 상황에서 입력으로 r, c, k가 주어진다. 1초마다 저런 움직임이 계속될 때, 맵에서 map [r][c] = k가 존재하는지, 존재한다면 몇 초 만에 가능한지를 구하는 문제이다. 문제 접근 단계 최우선적으로 보이는 것부터 정리해 보자면 (숫자, 그 숫자의 개수)라는 쌍이 존재..
문제 이해 단계 https://www.acmicpc.net/problem/15685 설명이 좀 어렵게 되어있는 문제. 모양이 이상하고 좀 이상하게 돌린다. 세대라고 해서 결국 레벨 같은 건데, 세대가 올라갈수록 이전의 했던 모양이 시계방향으로 90도 돌아간 채로 추가된다. 그렇게 점점 좌표계에서 많아지는데, 이건 그림을 보는 것이 훨씬 편하다. 들어오는 입력 정보로는 드래곤 커브의 x좌표와 y좌표, 움직일 방향, 그리고 몇 세대인지이다. 이렇게 여러 개의 입력정보가 들어와 여러 드래건 커브를 형성할 때, 맵에서 1x1 정사각형이 총 몇 개 나오는지 구하는 문제. 문제 접근 단계 문제가 좀 많이 어지럽다. 해당 그림을 배열을 만져가며 그리기에는 무리가 있다. 드래곤 커브가 만들어지는 원리에 집중했다. 드래..
문제 이해 단계 https://www.acmicpc.net/problem/20056 NxN인 격자에 M개의 파이어볼을 쏜다. 그리고 K번만큼 이동한다. 파이어볼은 5가지의 정보를 가지고 있는데, (x좌표, y좌표, 질량, 속력, 방향)이다. 1. 자신의 방향으로 자신의 속력만큼 움직인다. 2. 이동이 끝난 후 파이어볼이 같은 칸에 있는 것이 있다면 하위에 프로세스를 실행한다. 2 - 1. 같은 칸에 있는 파이어볼을 합한다.(질량, 속력 전부) 2 - 2. 합쳐진 파이어볼은 4개로 나뉜다. 2 - 3. 각 파이어볼의 속력은 (속력의 합/개수), 질량은 (질량의 합/5)이다. 2 - 4. 방향은 합쳐진 파이어볼의 각 방향이 모두 홀수거나 짝수면 0,2,4,6 그렇지 않으면 1,3,5,7이다. 2 - 5. 질..