공부공간

https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net N,M이 충분히 작기때문에 DFS로 상황을 만들고 정답이 될수있는지 구현하는 문제이다. 문제의 접근은 아래와 같이했다. MAP을 입력받고, MAP의 맨 마지막줄 N+1번째에 궁수를 3명 배치해야한다. 궁수는 N개중 순서상관없이 3명을 뽑는 것이므로, 비트마스크를 통해서 2중 FOR문으로 조합의 경우의 수를 뽑아낸후, MAP에 붙이고 계산하는 메소드에 넘겨준다. 입력으로 받은 D는 궁수가 공격을 할 수있는 최..

https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다. 수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9× www.acmicpc.net 수식에 괄호를 추가하여서 해당 부분을 먼저 계산하는 방식으로 수식을 변경하였을때 얻을 수 있는 최댓값을 구하는 문제이다. 입력받..

https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net DP는 너무나도 어려운것 같다. 점프는 맵에 표시된 수만큼 오른쪽과 아래로 점프한다. 최종 목적지까지 가는 경로를 찾아주면된다. 중간에 한 지..

준규는 1,1 에서 출발하여 주어진 N,M 까지 이동하며 이동하는 칸의 사탕을 가져간다. N,M 칸에 도달할 때 준규가 가질수 있는 최대의 사탕 개수를 도출하는 문제이다. 해당 문제의 접근법은 다음과 같다. 1. 이동하는 방법은 오른쪽, 아래, 오른쪽 대각선으로 정해져 있다. 2. 준규가 이동할 수 있는 미로 칸마다 사탕을 가져올 수 있는 최대값을 갱신하며 진행한다. 3. 최대값을 갱신할 때, 위 칸에서 내려오는 경우, 대각선 칸에서 내려오는 경우, 왼쪽 칸에서 오는 경우를 비교한다.

BOJ - 2293) 동전 1의 변형 문제이다. 동전 1의 경우, 주어진 금액을 나타내는 최대의 경우의 수를 출력하는 반면 동전 2의 경우 최소 경우의 수로 해당 금액을 나타내는 문제이다. 주의하여 생각해야할 점은 동전 1과 큰 차이가 없다. 1. 동전 1과 같이, 동전의 종류 별 경우의 수를 갱신한다. 2. 경우의 수를 갱신할 때, 배열 d 의 인덱스 값보다 적은 가치의 동전만을 생각한다. 3. 기존의 배열 d의 값과, 도출된 d 의 값을 비교하여, 적은 값을 선택한다. 4. 주어진 k 값이 도출되지 않을 경우(값이 갱신되지 않았을 경우) -1 을 출력한다. d[j] 의 값을 갱신할 때마다 기존의 d[j] 의 값과 배열에서 동전의 가치만큼 뺀 뒤 1을 더해준 값과 비교하여 더 작은 값을 갱신하고, 값이..

특정 금액을 다른 가치를 가진 동전으로 나타낼수 있는 최대 경우의 수를 구하는 문제이다. 기본적인 유형의 동적 프로그래밍 문제이다. 2중 for 문을 사용하여, 주어진 동전의 가치만을 사용할 때의 경우만 생각하며 일정 금액보다 사용할수 있는 동전의 가치가 낮은 경우, 동전의 가치를 뺀 경우의 수를 더하여 갱신함으로써 문제를 해결한다. ex) 4원을 위의 예제 입력으로 나타내는 경우, 예제의 1원만 사용할 경우를 생각하여 배열에 값을 갱신한다. i = 1) d[1]~d[4] = 1 i = 2) d[1] = 1, d[2] 의 경우 입력된 동전의 가치보다 크거나 같기 때문에, 기존의 d[2] 배열에 가지수를 추가하여 준다. d[4] = d[4](1로만 나타낸 경우의 수) + d[2](1과 2, 2로만 나타낸 ..

주어진 수를 제곱수로 나타낼 수 있는 최소의 항을 출력하는 문제이다. 주어진 수는, 주어진 수보다 작은 최대 제곱수의 경우 + 1의 규칙을 가지고 있다. 따라서, 해당 규칙을 만족하는 경우의 수가 현재 인덱스에 저장되어 있는 수보다 작다면, 갱신된다.

주어진 인덱스는 카드의 장수이고, 인덱스로 표기되는 팩에 따라 카드의 코스트를 입력 받는다. 원하는 카드의 개수 N 을 입력 받아 해당 카드의 개수를 구매할 때 금액의 최댓값을 출력하는 문제이다. 문제 해결에 대한 접근으로 2중 for 문을 사용하여, 원하는 카드를 구하기 까지 최대값을 갱신하도록 알고리즘을 작성한다. 카드의 구매 가능한 수에 따라, 해당 카드 팩을 구매했을 때와 그렇지 않을 때를 비교하여 최댓값을 갱신하여 준다. 카드 팩을 구매하였을 때는, 해당 카드팩의 카드 수를 빼준 최대값과 카드팩의 금액을 더한다.