반응형 브루트포스25 백준 1038번 감소하는 수 - C++(cpp) 풀이 1. 0-9 중 사용할 수들을 선택한 뒤, 큰 수부터 차례로 나열하면 감소하는 수가 만들어진다. 2. 따라서 감소하는 수의 총개수는 2^10-1 = 1023개 3. 감소하는 수를 모두 구한 뒤 정렬한다. 1. 0-9 중 사용할 수들을 선택한 뒤, 큰 수부터 차례로 나열하면 감소하는 수가 만들어진다. 숫자 목록이 주어지면 해당 수들로 만들 수 있는 감소하는 수는 하나로 결정된다. 또한 항상 감소해야 하므로 같은 숫자가 두 번 이상 등장하는 일은 없다. 따라서 10개 숫자 0-9에 대해 각각을 사용할 것인지를 결정하기만 하면 감소하는 수가 결정되고, 그 감소하는 수는 선택한 숫자들을 큰 수부터 차례로 나열한 것이 된다. 2. 따라서 감소하는 수의 총 개수는 2^10-1 = 1023개 10개 숫자에 대해 사용.. 2022. 3. 29. 백준 12169번 Infinite House of Pancakes - C++(cpp) 풀이 1. 노말 턴보다 스페셜 턴을 먼저 진행하는 게 더 이득이다. 따라서 스페셜 턴을 먼저 다 진행한 후 뒤에 노말 턴을 몰아서 진행한다. 2. 총 i번의 노말 턴을 진행하는 경우, 스페셜 턴을 전부 진행한 뒤 다이너들의 접시에는 전부 i개 이하의 팬케이크가 남아있어야 한다. 3. 총 i(1 ≤ i ≤ 1000) 번의 노말 턴을 진행하는 모든 경우를 고려하여 최솟값을 찾는다. 1. 노말 턴보다 스페셜 턴을 먼저 진행하는 게 더 이득이다. 따라서 스페셜 턴을 먼저 다 진행한 후 뒤에 노말 턴을 몰아서 진행한다. 노말 턴과 스페셜 턴을 한 번씩 진행해야 한다고 하자. 노말 턴 → 스페셜 턴의 순서로 진행할 때보다, 스페셜 턴 → 노말 턴의 순서로 진행할 때 같거나 더 적은 시간이 든다. 현재 다이너가 d명 있다.. 2022. 3. 25. 백준 3259번 PEOPLE - C++(cpp) 풀이 1. N명의 거짓말쟁이 여부를 결정하는 모든 경우, 2^N가지를 전부 체크한다. 2. 어떠한 경우가 해가 되려면, 해당 경우를 기준으로 했을 때 모든 사람들의 진술에 모순이 없어야 한다. 1. N명의 거짓말쟁이 여부를 결정하는 모든 경우, 2^N가지를 전부 체크한다. N명의 거짓말쟁이 여부를 결정하는 모든 경우는 총 2^N가지이다. 각 경우가 유효한지 체크하는 데 O(2N)의 시간 복잡도가 소요되므로, 전체 시간 복잡도는 O(2N*2^N)이다. N이 최대 20밖에 되지 않으므로 브루트포스로도 해결이 가능하다. 2. 어떠한 경우가 해가 되려면, 해당 경우를 기준으로 했을 때 모든 사람들의 진술에 모순이 없어야 한다. 어떠한 경우가 유효한지 체크하려면, 해당 경우를 기준으로 모든 사람들의 진술에 모순이 존재.. 2022. 3. 18. 백준 11277번 2-SAT - 1 - 스위프트(Swift) 풀이 1. 변수가 최대 20개이므로, 각 변수의 값을 정하는 모든 경우의 수는 2^20이다. 2. 비트마스킹을 사용하여 모든 경우를 계산해 결과가 true가 되는 경우가 존재하는지 확인한다. 1. 변수가 최대 20개이므로, 각 변수의 값을 정하는 모든 경우의 수는 2^20이다. 변수의 개수가 20개로 매우 작기 때문에 모든 경우를 고려해볼 수 있다. 각 변수마다 true/false 값 중 하나를 가지므로 모든 경우의 수는 2^20이다. 또한 각 경우의 결과값을 계산하는데 O(M)의 시간복잡도가 든다. 따라서 총 시간복잡도는 O(2^N*M). 2. 비트마스킹을 사용하여 모든 경우를 계산해 결과가 true가 되는 경우가 존재하는지 확인한다. Xi를 i번째 비트로 표현한다고 하면, 모든 변수가 false인 경우는 .. 2022. 3. 10. 백준 16637번 괄호 추가하기 - C++(cpp) 풀이 + 그림 설명 1. 앞에서부터 차례로 괄호를 하는 경우와 안 하는 경우를 모두 고려한다. 2. 수식의 끝까지 고려했으면 현재 계산 값을 가지고 최댓값을 갱신한다. 1. 앞에서부터 차례로 괄호를 하는 경우와 안하는 경우를 모두 고려한다. N=19밖에 되지 않으므로 대충 연산자 한 개마다 괄호를 할지 말 지를 결정한다고 쳐도 2^9가지밖에 나오지 않는다. 따라서 완전 탐색으로 풀 수 있다. 앞에서부터 차례로 괄호를 하는 경우와 안하는 경우를 모두 고려해준다. 괄호를 하지 않는 경우 그냥 순차적으로 가장 앞에 있는 두 수를 계산해주면 된다. 반대로 괄호를 하는 경우에는 맨 앞의 두 수를 연산하지 않고, 두번째 수와 세 번째 수를 먼저 계산한 후, 그 결과와 첫 번째 수를 연산해준다. 2. 수식의 끝까지 고려했으면 현재 계산.. 2022. 2. 18. 이전 1 2 3 4 5 다음 반응형
