브루트포스8 [백준 1248] 맞춰봐 www.acmicpc.net/problem/1248 1248번: 맞춰봐 규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느 날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 수도 www.acmicpc.net 순열로 풀었다가 틀렸다.... 중복 순열로 푸는 문제이다. n개의 숫자가 모두 같을 수도 있기 때문이다. 중복 순열 구현부 선택한 숫자를 cnt 번째 selected 배열에 넣고 다음 턴으로 넘긴다. for (int i = -10; i 0) { return '+'; } else if (a < 0) { return '-'; } else { return '0'; } } bool isValid(int col) { .. 2021. 3. 1. [백준 16986]인싸들의 가위바위보 www.acmicpc.net/problem/16986 16986번: 인싸들의 가위바위보 두 사람이 같은 손동작을 내어 무승부가 발생할 경우 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주함에 다시 한 번 유의한다. 구체적으로, 경기 진행 순서는 지우, 경희, 민호 순으로 고정되 www.acmicpc.net 낼 수 있는 손동작이 총 9개 이므로 브루트포스를 사용해서 모든 경우의 수를 확인하는 문제이다. 지우가 모든 손동작을 다르게 내어 우승할 수 있으면 1을, 그렇지 않으면 0을 출력한다. 지우가 내는 손동작이 모두 달라야 하므로 순열을 사용했다. next_permutation(배열 혹은 벡터의 시작점, 배열 혹은 벡터의 마지막 점) 순열을 구한 후 다음 순열이 존재하면 true 그렇지 않으면 false를.. 2021. 3. 1. [백준 10971] 외판원 순회2 www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 브루트 포스 문제의 일종이다. np problem중 하나로 인터넷에 검색해보면 dp + bit mask로 많은 풀이가 있다. dp와 bit를 사용해서 풀기 전에 일반적인 dfs접근을 해보려고 한다. 문제에 대한 분석 1. 외판원 순회 문제 모든 도시들을 한번만 방문하여 처음 출발한 도시로 돌아올 때 최소 비용을 구하는 문제이다. 2. 출발 도시는 상관없다. 왜냐 어차.. 2021. 2. 5. [백준 1543] 문서 검색 www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 브루트포스를 돌면 tle가 아닐까..했으나 길이가 짧아서 아닌거 같다. 접근 방식은 간단하다. 모든 문자열 비교 - 브루트포스이다. 처음엔 0부터 비교하는 걸로 했으나 반례가 존재했다. ababaa abaa 같은 로직으로 앞에서 부터 비교를 시작하면 aba까지 체크하고 a와 b가 달라서 지나가버리지만 뒤에서 부터 비교하면 abaa를 잡아낼 수 있다. 공백이 포함된 입력값도 제공되므로 getline(cin, 문자열)을.. 2020. 12. 16. 이전 1 2 다음