[BOJ] 괄호 추가하기

[haesoooo]

문제 링크

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

풀이 사항

풀이 일자: 2024.00.00 풀이 시간: 00분 00초 채점 결과: 오답/시간 초과/런타임 에러/정답 예상 문제 유형: 구현/BFS/DFS/DP/자료구조/문자열 등 시간: 00 ms 메모리: 00 kb

풀이 방법

(풀이 접근 및 방법에 대한 설명 문제를 풀지 못했다면 어느 곳에서 어려움을 느꼈는지 적어주세요!!)

[haesoooo]

문제 링크

491

풀이 사항

풀이 일자: 2024.11.12 풀이 시간: 2시간 채점 결과: 정답 예상 문제: 부분집합 시간: 0 ms 메모리: 2024 kb

풀이 방법

숫자를 선택 -> visited를 true 선택하지 않음 -> visited를 false

• 현재 인덱스의 숫자를 선택 (괄호 안에 포함하겠다) 하면, 바로 다음 숫자까지 묶어서 괄호를 쳐야하므로 다다음 인덱스(idx + 2)로 넘어가서 재귀
• 현재 인덱스의 숫자를 선택하지 않으면, 다음 숫자를 선택할 수도 있으므로 다음 인덱스 (idx + 1)로 넘어가서 재귀

마지막 인덱스에 도달하면, visited true인 숫자에 한해서 괄호 계산을 먼저 해줌

• ex) 8 3 + 5 에서 (8 3) + 5 라면 visited 배열은 1 1 0, num은 8 3 5 -> 계산한 값을 num에 다시 저장 -> 24 24 5 visited false인 숫자에 대해서는 이후에 계산
• ex) 24 24 5 에서 24 + 5 진행 -> 24 29 29 최종 값은 num[num.size() - 1] 에 담긴 값을 보면 됨

느낀 점

백트래킹은 정말 어떤 것을 파라미터로 넘기고 원복할 지를 결정하는 게 어렵다.