brute force
-
[SWEA] 2112. 보호필름문제 풀이 2020. 5. 4. 18:27
2212 보호필름 풀이)재귀 + 브루트 포스 문제였다. 필름 막 상태를 vector arr;에 저장해 놓았다.그리고 약품으로 막 상태를 바꾼다면 기존의 값을 알아놔야하기 때문에 처음에는vector temp =arr; 로 전체 상태를 저장해놓은 뒤,막 상태 바꾼 후 arr= temp; 로 돌려놓았는데 이렇게 하니 시간초과가 났다. 아무래도 백터 전체를 저장하고 돌려놓고 해서 그런듯 싶어 두번째로는 필름 막 상태 모두를 저장해놓지 않고,기존의 막 상태(행)만 저장해두고 vector temp = arr[i]; (i는 바꿀 막 인덱스)상태 바꾼 후 원래 막 상태로 바꿔주도록 했더니 arr[i] = temp;시간 초과가 나지 않고 통과했다. 시간초과가 나지 않게 사용한 방법은 위에서 설명한 거 말고 2가지가 더있..
-
[SWEA] 2806 N-Queen문제 풀이 2020. 4. 23. 00:13
2806 N-Queen 풀이) 완전 탐색 문제이고,퀸이 같은 행, 열 또는 대각선에 놓일 수 없다는 점을 잘 생각해서 풀면 되는 문제이다. 퀸은 같은 행에 놓일 수 없다 ↓ 한 행 당 하나의 퀸만 놓일 수 있다. 를 기준으로 각 행 당 어떤 열에 퀸을 놓을 때, 이전 행들이 퀸을 놓은 열과 직선인지 혹은이전 행들이 퀸을 놓은 열과 대각선인지 를 확인해서 두 경우에 해당하지 않는 경우에만 퀸을 놓아줬다. (이전 행들이 퀸을 놓은 열들은 1차원 배열을 통해 저장해줬다.int row[10] // row[i] = j -> i번째 row j번째 column에 퀸이 놓여졌다.) 코드) 1234567891011121314151617181920212223242526272829303132333435363738394041..
-
[백준] 1062번 가르침문제 풀이 2020. 4. 4. 16:38
1062 가르침 문제남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오. 입력첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다..
-
[백준] 1107번 리모컨문제 풀이 2020. 4. 3. 20:11
1107 리모컨 문제수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 수빈이가 지금 보고 있는 채널은 100번이다. 입력첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 ..
-
[백준] 1182번 부분수열의 합문제 풀이 2020. 4. 1. 22:52
1182 부분수열의 합 문제N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. 출력첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.풀이) 모든 경우를 다 확인하는 brute force문제이다.재귀적 방법을 이용하였다. 예를 들어 5개의 원소가 주어지고 합이 100인 부분수열을 찾는다면 원소10 20 30 40 50 인덱스01234 수열 크기 1일때 -> {10},{20..