문제링크 : https://www.acmicpc.net/problem/7490
해결방법 :
1 부터 N까지 -, +, " " 의 연산을 사이에 각각 넣어서 최종 합이 0이 되는 식을 모두 출력하는 문제다.
일단 식을 누적하는 변수 str, 최종합을 누적하는 변수 sum을 설정하고 생각해봤다.
자연스레 3가지경우에 대해 재귀호출을 하면 모든 경우를 만들 수 있기에 3가지의 재귀함수를 설계하면 답을 구할 수 있다.
여기서 ""연산에 대해 주의할 점이 있는데,
다음 재귀에 +나 -를 만나면 이전의 값(num)을 sum에 더해주거나 빼준다. 그전에는 sum에 아무런 계산하지 않는다.
이말은 ""로 된부분은 num에 합쳐진숫자로 업데이트만 하고, 다음에 +나-가 오면 계산을 해준다는 것이다.
나머지 -, +의 경우에는 다음에도 -,+일때 sum에 num*sign 값을 더해준다. 참고로 sign을 곱해주고 더해주면서 뺄셈을 한다.
재귀함수로 넘겨주는 값을 보면 이해가 될것이다.
소스코드)
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 | #include<iostream> #include<string> using namespace std; int N; void solve(int sum, int sign, int num, int n, string str) { //1부터 N까지 숫자를 3가지연산을 해서 0으로 되는 식을 모두 출력하는 함수 if (n == N) { sum += (num * sign); if (sum == 0) { cout << str << '\n'; } } else { solve(sum, sign, num * 10 + (n + 1), n + 1, str + ' ' + char(n + 1 + '0')); solve(sum + (sign*num), 1, n + 1, n + 1, str + '+' + char(n + 1 + '0')); solve(sum + (sign*num), -1, n + 1, n + 1, str + '-' + char(n + 1 + '0')); } } int main() { int test_case; char test; scanf("%d", &test_case); for (int i = 0; i < test_case; i++) { scanf("%d", &N); solve(0, 1, 1, 1, "1");// sum, sign, num, n, str printf("\n"); } return 0; } | cs |
반응형
'PS > 백준' 카테고리의 다른 글
| 1932번 정수삼각형 (0) | 2018.12.30 |
|---|---|
| 1149번 RGB거리 (0) | 2018.12.05 |
| 1003번 피보나치 함수 (0) | 2018.12.02 |
| 1065번 한수 (0) | 2018.11.16 |
| 1110번 더하기 사이클 (0) | 2018.11.14 |