<링크>
https://www.acmicpc.net/problem/14888
<소스코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #include<stdio.h> int num[11]; int opCnt[4]; int N; int min=1100000000, max=-1100000000; void recur(int, int); int main() { scanf("%d", &N); for (int i = 0; i < N; ++i) scanf("%d", num + i); for (int i = 0; i < 4; ++i) scanf("%d", opCnt + i); recur(num[0], 1); printf("%d\n%d", max, min); } void recur(int res,int k) { if (k == N) { if (res > max) max = res; if (res < min) min = res; } for (int i = 0; i < 4; ++i) { if (opCnt[i]) { --opCnt[i]; switch (i) { case 0:recur(res + num[k], k + 1); break; case 1:recur(res - num[k], k + 1); break; case 2:recur(res*num[k], k + 1); break; case 3:recur(res / num[k], k + 1); break; } ++opCnt[i]; } } } | cs |
<풀이>
opCnt배열에 각 연산자 기호의 개수를 입력받는다.
예를 들어
+ - * /
2 1 0 1
이라면,
++-/
++/-
+-+/
+-/+
+/+-
+/-+
...
/+-+
/-++
처럼
모든 가능한 연산자 순서를 다 적용시켜서 나오는 결과값을 보면 된다.
순열과 비슷하지만 한 연산자가 여러 개 있을 수 있기 때문에
각각의 연산자 cnt를 감소시키며 dfs를 하고, cnt가 0이 되면 해당 연산자는 다 본 것이기 때문에 넘어간다.
호출되기 직전에 cnt를 감소시켜주고, 호출이 끝나면 다시 cnt를 증가시켜줘야한다.
이는 순열만들기의 dfs에서 visit를 체크하는 방법과 유사하다.
자신이 사용했다가 끝나면 다시 원상복귀를 시켜줘야 나중에 사용할 때 문제가 없다.
'알고리즘 풀이 > 브루트 포스' 카테고리의 다른 글
| 백준 15686 치킨배달 (0) | 2018.09.30 |
|---|---|
| 백준 1107 리모컨 (2) | 2018.07.26 |
| KOITP 고장난시계 (0) | 2018.07.23 |
| 백준 1421 나무꾼 이다솜 ::들짐승 (0) | 2018.07.22 |