백준/DP13

• 

  [백준 12869번 / C++] 뮤탈리스크 스타크래프트를 즐겨하는 사람으로서 뮤탈리스크란 문제를 보고 호기심때문에 풀어봤다. (난 테란 유저이기 때문에 뮤탈리스크를 매우 싫어한다.) 1. 사기 유닛 뮤탈리스크는 소중한 SCV를 최대 3마리까지 공격 가능하다. 순서에 따른 공격 데미지는 총 6가지의 경우가 있으므로 이차원 벡터에 저장하였다. 2. 최대 3마리까지 공격 가능하니 3차원 dp배열을 생성하여 해당 배열에 최소 공격횟수를 저장해준다. 3. 이후 다른 재귀에서 해당 dp배열을 참조할 시 기록해 뒀던 값을 반환하여 사용하면 된다. * 본인은 next_permutation 함수를 활용하여 완전 탐색으로 구현을 시도했지만 시간 초과가 발생하여 3차원 DP를 활용하였다. #include #include #include #include #includ.. 백준/DP 2022. 2. 9.

• [백준 1450번 / C++] 냅색문제 이 문제는 상당히 까다로운 문제이니, " n = 4 , c = 3, v = [1,2,3,4]" 라는 값으로 재귀가 어떻게 돌아가는지 코드를 보고 그림으로 한번 표현해보자. part1 / part2로 나뉘어서 진행 part1을 예로 들어서 설명하겠다. part1에는 현재 [1,2] 라는 무게를 담고 있고 재귀를 도는데 "1"의 무게를 가진 놈을 담아? Yes or No (2가지) "2"의 무게를 가진 놈을 담아? Yes or No (2가지) 위의 경우를 가지치기로 만들어진 sum의 개수는 2X2 = 4 가지 이며, part1의 sum값은 [ 0, 2, 1, 3] 이 된다. part2의 sum값은 [0, 4, 3, 7] 이 된다. part2는 오름차순으로 정렬을 시킨다. [0, 3, 4, 7] 여기서 par.. 백준/DP 2022. 1. 26.

• 

  [백준 1103번 / C++] 게임 쉽게 생각하고 dfs를 적용해서 해보니 메모리 초과가 떴다. 즉, 50X50 배열에서 값에 따른 재귀를 계속 호출하면서 스택에 함수가 계속 쌓이게 된다. 이로인해서 메모리 초과가 발생하게 되는것이다. 그렇기 때문에 방문 했던 곳에 대한 카운트 값을 기록 즉, 메모이제이션 DP를 활용해야했던 문제였다. 먼저, 다음 그림의 예제값으로 그림을 그려보자. (0,0) 좌표에 해당하는 값은 "2" 이다. 그렇다면 상하좌우를 살펴보면서 갈 수 있는 길을 찾게 된다. 나아가야 할 방향의 순서를 "우좌상하" 라고 가정하고 한번 풀어보겠다. 그렇다면 먼저 오른쪽 방향으로 먼저 가보겠다. 이때 vsited(좌표값) 에 방문했다고 체크를 해두자. 오른쪽 방향에서 만나는 숫자는 3이다. 여기서도 똑같이 vsited(좌표값) 에.. 백준/DP 2022. 1. 17.