https://www.acmicpc.net/problem/2529
모든 경우를 다 테스트해봐야하고, 순서가 상관 없다는 조건이 나오면 순열 문제라고 간주하면 된다.
0부터 9까지의 값 중 k+1개를 고르고, (k+1)! 순서를 모두 만들어 부등호를 검사한다. 이를 공식으로 표현하면 다음과 같다. ⇒ 2^(k+1) * (k+1)! * (k+1)
알고리즘 상에서는 각 숫자를 선택할 지, 안 할지 하나하나 결정하는 것이기 때문에 2^(k+1) 번의 선택 과정을 거치게 된다.
이 문제는 브루트 포스 문제로, 모든 케이스를 테스트해보며 문제의 조건(부등호)에 부합하는지 확인한다.
오답노트
int findMax(int previous, int index) {
if (index == k) return 0; // 모든 부등호를 탐색하였다면
int ret = 0; // 최댓값을 저장한다.
if (input[index] == '<') // 다음 값이 더 크다면
// 큰 값부터 탐색한다.
for (int next = 9; next > previous; next--)
if (!visited[next]) { // 선택하지 않은 값이라면
visited[next] = true;
ret += findMax(next, index +1) * pow(10, index - 1);
visited[next] = false;
}
else { // input = '>'
for (int next = previous - 1; next > 0; next--)
if (!visited[true]) {
visited[next] = true;
ret += findMax(next, index + 1) * pow(10, index - 1);
visited[next] = false;
}
}
return ret;
}
/*
최댓값을 찾는 방법
(1) 제일 큰 숫자부터 넣는다. 부등호의 방향에 따라 더 큰 수를, 혹은 더 작은 수를 넣는다.
(2) 다음 값(next)으로 들어갈 수 있는 숫자 중 가장 큰 숫자를 넣는다.
(3) 최솟값은 입력 배열에 -1을 곱해준 후 최댓값을 찾는 로직에 그대로 적용시킨다. 그리고 출력 값에 -1을 다시 곱한다.
궁금한 점
(1) 맨 처음 값은 어떻게 지정할지 ? (9부터 0까지 previous 를 넣어주며 10번 호출해야하는건가?)
(2) 제일 큰 값으로 채워놓다보면 못 채우는 경우가 생기는데, 이 경우를 어떻게 핸들링할 수 있는지 ? => for문에서 찾을 대상이 없으므로 바로 재귀를 종료하게 된다.
*/
next_permutation 이딴 함수가 있는 지 모르고 설계한 함수이다.
(1) 정수 변수를 10의 n승으로 매번 곱해주는 것을 구현하기 어려웠다. 이런 경우에는 배열로 값을 받고, 정수처럼 출력하는 방법이 더 쉽다.
(2) 재귀 함수의 정의를 제대로 내리지 않고 냅다 함수를 만들었음. 재귀함수를 쓰려면 재귀 함수가 어떤 input과 output을 가지는 지 명시할 것
// input의 부등호 조건과 일치하는 순열인지 검사
bool check(const vector<int> perm, vector<char> input) {
for (int i = 0; i < k; i++)
if (input[i] == '<' && perm[i] > perm[i + 1])
return false;
else
if (perm[i] < perm[i + 1])
return false;
return true;
}
추가로, if-else 문 실수를 해서 input[i] == '<'이지만 그 뒤 조건이 만족하지 않을 때 else문으로 내려오게 되는 버그를 가지는 프로그램을 만들었다. 여러 조건을 가지는 것을 만들 때는 논리 흐름을 꼭 시뮬레이션 할 것.
GCF + ACDEB = 783 + 98654 = 99437 수는 주어지는 게 아니라 내가 정해야 하는것
"숫자 조합"을 만들어서 최대가 되는 값으로 치환해야 한다.
G C F 3 2 1 A C D E B 5 4 3 2 1
vector<int>number;(1) 자릿수가 큰 문자열의 앞자리부터 순서대로 큰 숫자를 넣는다. G C F A C D E B 9 8 (2) 검사하지 않은 문자열의 크기가 모두 같아지면 가중치를 매기기 시작한다. D = 3 E = 2 B = 1 G = 3 F= 1 (3) 가중치 순으로 큰 숫자를 부여한다. 이때 같은 가중치라면 둘 중 어떤 것을 먼저 매기던 상관없다. G C F 7 8 3 A C D E B 9 8 6 5 49 9 4 3 7 (4) 이 로직이 다른 입력값에도 똑같이 적용되는 지 검토한다. A B 9 8 B A 8 9
187