문제 이해 단계 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. 돌..
문제 이해 단계 연속 부분 수열과 같은 길이의 펄스 수열이 존재한다. 펄스 수열 : {1,-1,1,-1...} or {-1,1,-1,1,-1..} 이런 식으로 1과 -1이 번갈아가며 나오는 수열 연속 부분 수열 : 한 수열에서 끊기지 않고 연속해서 나열되어 있는 수열 ex ) {4,5,-3,2,0,-2,-1,-2}에서 {4,5-3}, {0,-2}, {-2,-1,-2} , {-1}은 연속 부분 수열임 연속 부분 수열과 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만든다고 가정한다. 이때 나올 수 있는 부분 집합 중, 원소의 합이 가장 큰 부분 집합을 구해서 그때의 합을 구하는 문제 문제 접근 단계 이 문제를 복잡하게 하는 부분은 연속 부분 수열의 시작점을 모른다는 것과 펄스 수열이 -1로 시작할..
문제 이해 단계 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가 존재하는지, 존재한다면 몇 초 만에 가능한지를 구하는 문제이다. 문제 접근 단계 최우선적으로 보이는 것부터 정리해 보자면 (숫자, 그 숫자의 개수)라는 쌍이 존재..
정렬(sort) - compare C++에서 자주 쓰이는 기능 중, 헤더 안에 있는 sort 기능이 많이 쓰인다. 해당 함수는 벡터(vector)나 배열과 함께 사용한다. 아래는 사용법 예시이다. #include #include // sort 헤더파일 #include // 벡터 헤더파일 using namespace std; int array_size = 8; int main(){ int array[] = {4,5,2,1,5,1,74,5}; vector arr = {4,5,2,1,5,1,74,5}; sort(arr.begin(),arr.end()); sort(array,array+array_size,greater()); for(int i = 0; i < arr.size(); i++) { cout
문제 이해 단계 https://www.acmicpc.net/problem/15685 설명이 좀 어렵게 되어있는 문제. 모양이 이상하고 좀 이상하게 돌린다. 세대라고 해서 결국 레벨 같은 건데, 세대가 올라갈수록 이전의 했던 모양이 시계방향으로 90도 돌아간 채로 추가된다. 그렇게 점점 좌표계에서 많아지는데, 이건 그림을 보는 것이 훨씬 편하다. 들어오는 입력 정보로는 드래곤 커브의 x좌표와 y좌표, 움직일 방향, 그리고 몇 세대인지이다. 이렇게 여러 개의 입력정보가 들어와 여러 드래건 커브를 형성할 때, 맵에서 1x1 정사각형이 총 몇 개 나오는지 구하는 문제. 문제 접근 단계 문제가 좀 많이 어지럽다. 해당 그림을 배열을 만져가며 그리기에는 무리가 있다. 드래곤 커브가 만들어지는 원리에 집중했다. 드래..