문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 이 문제는 동적계획법으로 풀이하였다. 풀이 방법 이 문제의 분기점은 처음 도둑질을 할 때, 첫 번째 집을 고르냐, 두 번째 집을 고르냐에 따라 크게 두가지로 나뉜다. 인접한 집은 털 수 없다는 제한으로 두 경우로 나뉘어 집을 터는 루트가 정해지기 때문이다. 필자의 풀이 방법을 그림을 통해 자세히 보도록 하자. 왼쪽에 보이는대로, 처음 세 개의 집은 터는..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr Dynamic Programming(동적 계획법)을 이용하여 풀었다. 풀이 방식 개인적으로 로직을 짜기 제일 까다로웠던 문제중 하나였던 것 같다. 필자는 이 문제를 'N을 사용한 횟수'를 기준으로 나눠 풀이하였다. 즉 N이 5라면, 5를 1번, 2번, 3번...8번(문제 조건에 8보다 크면 -1리턴이기 떄문)사용해서 만들 수 있는 숫자들의 경우로 나눈 것이다. 박스가 8개 있다고 해보자. 1번 박스에는 N을 1번 사용해서 만들 수 있는 숫자들이 담겨있다. N = 5라고 한다면 1번 박스에는 5만 담겨있을 것이다. 2번 박스에서는 ..