문제풀이9_DFS) 연산자 끼워넣기

Intro

S기업 코딩테스트 대비를 계속한다.

백준 사이트의 문제 링크를 첨부한다.

https://www.acmicpc.net/problem/14888

간단하게 문제를 설명하자면,

정수로 이루어진 수열 A가 주어지고,

연산자 +, -, *, / 의 갯수가 주어진다.

연산자 우선순위를 무시하고 앞에서부터 계산하며, 수의 순서 또한 바뀌지 않는다.

연산자 만 이리저리 옮겨가며 계산하면 된다.

Solution

dfs를 사용하면 쉽게 풀 수 있을 것으로 생각했다.

연산자의 우선순위를 생각하지 않아도 되기 때문에, 수열에서 현재 인덱스에 해당하는 값과, 다음 인덱스를 계산한 결과값을 인자로 넘겨주며 dfs를 다시 호출했다.

마지막 인덱스의 수열까지 연산자를 뽑아 계산했다면 최댓값, 최솟값을 결정한다.

Code

Conclusion

계산하는 값들의 범위가 -10억~10억 이므로 long long 타입을 사용했는데, 굳이 그러지 않아도 결과값은 나오는 것 같다.

s기업은 같은유형의 기출문제가 많이 나왔기 때문에, 많이 익숙해져서 금방 에러 없이 풀 수 있게 된거같아 자신감이 많이 생겼다.

개인적으로 dfs를 backup - dfs() - load 방식으로 틀을 잡고 구현을 하는데,

이번 문제 에서는 중간중간 계산하며 인자로 넘어가는 변수 res 값에 대한 backup을 제대로 하지 않았기 때문에 에러가 한번 발생했다.

세세한 것까지 신경쓰는 노력이 필요하다.