전체 글

문제에서 제시한 최대 SCV는 3마리 이다. 세마리의 SCV가 있다고 하자. 뮤탈의 쓰리쿠션 공격 방법은 모두 6가지 이다. A -> B -> C A -> C -> B B -> A -> C B -> C -> A C -> A -> B C -> B -> A 이 6 가지 경우로 재귀호출을 계속 하게 되면 언젠가 SCV 3마리의 체력이 모두 0이하가 될 것이다. 재귀 호출의 Depth 자체가 공격회수와 같다고 볼수있으므로, 이를 비교해 최소값을 구하면 된다. 코드를 구현하면 다음과 같다. SCV의 체력이 음수가 될수 있음에 유의한다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include int Max = 0x7FFFFFFF; using name..

동적계획법을 이용하면 쉽게 해결이 가능한 문제이다. 웍의 경우는 동시에 2개를 사용이 가능하므로, 웍의 조합으로 새로운 크기의 웍을 만들고 반복문을 이용해 동적계획법을 사용한다. N 그릇을 요리한다고 할때, 내가 가진 웍의 크기가 각각 3 4 5 6 이라고 하자. 그렇다면 요리횟수의 최소값은 (N - 3) 그릇을 요리하는 회수 + 1 (N - 4) 그릇을 요리하는 회수 + 1 (N - 5) 그릇을 요리하는 회수 + 1 (N - 6) 그릇을 요리하는 회수 + 1 중 하나이다. 코드로 구현하면 다음과 같다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; std::vector Works; bool ..

동적 계획법을 이용해야 하는 문제이다. 이전의 답이 다음의 답을 정한다. 수열을 만들때 1 또는 00 만 선택할 수 있다. N = 1 , N = 2 일 만들수 있는 수열은 각각 1 그리고 11,00 이다. 이제 3일때 부터가 중요하다. 길이가 3인 수열을 만들기 위해서는 길이가 2인 수열에 1을 추가를 하던지, 길이가 1인 수열에 00을 추가하던지, 11을 추가해야한다. 그런데 잘 생각을 해보면 길이가 1인 수열의 원소의 뒤에 11을 붙이면 경우는 길이가 2인 수열에서 1을 붙인것 과 겹친다. 길이가 N인 수열은 길이가 N-2인 수열의 개수 + 길이가 N-1인 수열의 개수 와 같다. WHY ? N-1 수열에는 N-2 에서 1을 추가해 만든 수열이 포함되어 있음을 기억하자. 따라서 N-2 수열에서는 무조건..

인원을 구성하는 문제 역시 Back Tracking 을 이용한 완전탐색 문제의 대표적인 예이다. 문제를 보면 같은 인원수를 원하고 있다. 10 명 중 5명을 골라서 팀을 이루면 나머지는 자동적 으로 정해지는 것이 아닌가? 따라서 재귀호출의 Depth는 선수의 수를 2로 나눈 값이 된다. 이제 재귀 함수를 만드려고 한다. 헌데 한가지 고민이 생긴다. A B 로 팀을 만들면 함수는 리턴한다. 상대팀은 자동적으로 C D 가 된다. C D 로 팀을 만들면 함수는 리턴한다. 상대팀은 자동적으로 A B 가 된다. 팀 이름만 달라지고 결국 같은 답을 두번 구하게 되는것이다. 그래서 한번 Depth의 끝에 도달하면 두개의 팀 모두의 능력치를 저장한다. A B 팀일때 C D 가 한팀이 된다. 이때 A B 를 가진 팀의 ..

동적계획법을 사용한다는 것은 이전의 연산결과를 통해 다음의 연산결과를 구해내겠다는 것이다. 위의 피보나치 함수의 예는 아주 간단하고도 대표적인 예이다. 위 함수를 F(N) 이라고 부른다고 하자. F(N) 은 F(N-1) 과 F(N-2) 를 호출한다. 그렇다면 F(N-1) 은 F(N-2)와 F(N-3)을 , F(N-2)는 F(N-3)과 F(N-4)를 호출 한다. 위의 조건을 보면 F(1)일때는 1을 출력한다. F(0)일때는 0을 출력한다. 그러면 F(2)는 ?? 1과 0을 1개씩 출력하는 것 이다. 조금만 더 계산해보면 F(3)은 F(2)의 결과 (1 과 0 각각 1개씩) 을 출력하되 F(1)의 것 (1만 1개)을 출력한다. F(4) 의 경우는 ? F(3)의 결과값에 , F(2) 결과값이 합쳐진 것이 결과..