문제 요약문제 링크: https://www.acmicpc.net/problem/9655 돌 게임은 두 명이서 즐기는 재밌는 게임이다.탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오.게임은 상근이가 먼저 시작한다.상근이가 게임을 이기면 `SK`를, 창영이가 게임을 이기면 `CY`을 출력사고 정리 예제를 기준으로 천천히 접근해보자. dp_table을 만들거고 bottom-up 방식으로 진행하고자 한다. 주어진 돌의 개수가 5개이고 상근이가 게임을 시작한다.상근이는 돌을 1개 혹은 3개를 가져갈 수 있다.더보기시..

문제 요약N가지 종류의 화폐가 있다.이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다.이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.사고 정리 DP 문제를 풀때 무조건 dp_table을 만든다고 생각하고 이 dp_table이 어떤 것을 의미할지 고민하는 연습을 하니 조금 감은 잡았던 문제였던 것 같다. dp_table의 index는 index원을 만들려고 하는 것이고 그 배열의 값을 최소 동전 개수라고 생각하자. 그 중에서 최소 동전이기 때문에 기존에 0으로 초기화하던게 아니라 최댓..

문제 요약가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1X2의 덮개, 2X1의 덮개, 2X2의 덮개를 이용해 채우고자한다. 이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오.예를 들어 2X3 크기의 바닥을 채우는 경우의 수는 5가지이다. 사고 정리 DP 문제 풀이는 아무래도 익숙해져야 좀 딱딱 생각날 것 같은 느낌이 든 .. ㅎ 큰 문제를 작은 문제로 나눈다고 생각하고 직접 그림을 그려보면서 경우의 수를 생각해보는게 도움이 되는 것 같다. (아마?)이 문제도 dp_table의 index는 주어진 값에 바뀌는 가로의 길이 N이라고 생각하자. 그리고 왼쪽에서부터 하나하나 덮개를 채워나간다고 생각하면 되는데, 초기의 값은 두가지 경우이다...

문제 요약개미전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하자.{1, 3, 1, 5}이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 ..

문제 요약정수 X가 주어질때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.X가 5로 나누어떨어지면, 5로 나눈다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.X에서 1을 뺀다.정수 X가 주어졌을때, 연산 4개를 적절히 사용해서 1을 만들려고 한다.연산을 사용하는 횟수의 최솟값을 출력하시오.예를 들어, 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다.26 - 1 = 2525 / 5 = 55 / 5 = 1사고 정리 오랜만에 풀어보는 DP라서 그런지 처음에는 약간 뭐 어쩌라는거지? 싶긴했다. `이것이 코딩테스트다` 책에서 언급하듯 버텀업 방식으로 풀이하는게 맞을 것 같아서 아래와 같이 풀이했다. dp_table을 우선 만들어두고, 각 inde..

Background다양한 문제들을 풀이할 때 컴퓨터를 활용해도 풀이하기 어려운 문제들이 있다.예를 들어, 최적의 해를 구하기 위해 많은 시간 혹은 많은 메모리 공간이 필요한 경우이다.이런 경우 메모리 공간을 조금만 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있으며 그 방법이 이번에 다루는 다이나믹 프로그래밍 (Dynamic Programminig), DP 라고도 표현한다.이것이 코딩테스다 책을 기준으로 간단하게 내용 정리를 해보도록 하겠다.해당 책에서는 피보나치 수열 문제를 이용하여 DP를 이해시켜주고 있다. DP란?다이나믹 프로그래밍으로 문제를 풀이하기 위해서는 아래 조건을 만족해야한다.큰 문제를 작은 문제로 나눌 수 있다.작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.그리고 ..