문제 이해 단계 https://www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net N개의 단원과 사용할 수 있는 총 시간 T가 입력으로 주어진다. 둘째 줄에는 각 단원에 대해서 공부하는데 걸리는 예상 시간과 배점이 입력으로 들어온다. 해당 조건에서 총 시간 T를 분배해서 각 단원을 공부하여 배점을 얻을 때 얻을 수 있는 최대 점수를 구하는 문제 문제 접근 단계 최대 점수를 구하는 문제라길래, 처음에는 그리디 문제가 아..

문제 이해 단계 https://www.acmicpc.net/problem/14945 14945번: 불장난 랩실의 크기가 3일 경우 (기웅, 민수)가 이동 가능한 방법은 (아래-아래, 대각-아래), (아래-아래, 대각-대각), (아래-대각, 대각-대각), (대각-아래, 아래-아래), (대각-대각, 아래-아래), (대각-대각, www.acmicpc.net 불이 있는 가장 위에서부터 시작해서 1초마다 아래, 오른쪽 아래, 왼쪽 아래로 퍼진다. 그리고 기웅, 민수도 위에서부터 시작하는데 이동 가능한 방법은 아래로 움직이거나, 오른쪽 아래로 움직이는 2가지다. 기웅, 민수는 맨 위 칸을 제외하고는 이동 중에 겹쳐서는 안 된다. 입력으로 n이 주어지고 직각삼각형으로 위의 그림처럼 주어진다. 항상 가장 마지막 n칸에..

문제 이해 단계 https://www.acmicpc.net/problem/13910 13910번: 개업 해빈이는 짜장면을 정말 좋아한다. 짜장면을 너무 좋아한 나머지 짜장면만 파는 중국집을 개업했다! 해빈이는 양손잡이여서 동시에 두 개의 웍(중국 냄비)을 사용하여 요리할 수 있다. 그러나 www.acmicpc.net 문제는 그렇게 복잡하지 않다. N개의 짜장면을 M개의 웍을 가지고 만들어야 한다. 각각의 웍은 짜장면을 만들 수 있는 용량을 가지고 있고, N개의 짜장면을 만들 때 정확하게 N개만 만들어야 한다. 이때 한번 요리할 때 M개의 웍 중 1개 또는 2개씩 선택할 수 있을 때, 최소한의 횟수로 요리를 만들 때 그 횟수를 구하는 문제 문제 접근 단계 요리 횟수 통일하기 일단 문제의 조건부터 살펴보면 ..

문제 이해 단계 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. 돌..

문제 이해 단계 연속 부분 수열과 같은 길이의 펄스 수열이 존재한다. 펄스 수열 : {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개의 칸에..