9. [백준 14888번 / C++] 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

 

이쯤되면 알 수 있는게 삼성은 백트래킹을 굉장히 좋아하는 것 같다. 아, 구현도

 

이 문제를 처음 읽었을 때는 백트래킹을 이용해서 풀어봐야겠다고 생각이 든다. 근데 실제로도 그랬다.

 

N의 범위가 2 <= N <= 11이기 때문에 백트래킹을 이용해서 풀어도 공간적으로나 시간적으로나 매우 여유가 있다.

 

물론 다른 풀이도 있겠지만 풀 때 시간 제한을 강하게 두고 빨리 풀려고 노력중이여서 백트래킹으로 풀었다.

 

간단하게 주어진 숫자들을 하나씩 탐색하면서 문제 그대로 각 사이에 "연산자 끼워넣기"를 시도한다. +을 넣어보고 백트래킹으로 다시 돌리고 -을 넣어보고 백트래킹으로 다시 돌리는 작업을 반복한다.

 

사실 이전에 한 번 풀어본 문제긴하다... 까먹고 있었는데 이전 강의에서 풀어봤더라! 그래서 코드는 스킵...