99클럽 코테 스터디 18일차 TIL - 42895 N으로 표현

42895. N으로 표현 / c++ / level3 / 1시간+

문제 및 코드

접근 방식

동적 계획법

1. 사칙 연산으로 이루어져 있다는 점에서 착안
2. N이 들어간 횟수를 i라고 했을 때, i + 1은 결국 1 ~ (i-1)까지의 사칙 연산으로 이루어져 있다고 판단
3. dp[i]는 N이 i번 들어갔을 때 만들어질 수 있는 수들의 배열 (여기선 중복을 방지하기 위해 unordered_set을 사용)
4. i 를 1부터 8까지 증가시켜가면서, i를 이룰 수 있는 경우의 수 (i가 4라면 1 + 3 부터 3 + 1) 까지의 두 수 j, k를 인덱스로 하는 dp[j], dp[k]를 가져와서, 거기에 해당하는 모든 수의 사칙 연산을 다시 dp[i]에 삽입 (이 때, 0보다 클 경우에만 삽입)
5. 그리고 여기서부터는 막혀서 결국 다른 코드를 보고 깨달았음
6. 기존엔 32,001 보다 작아야 dp[i]에 삽입했었는데, 그건 단지 number가 32’000이하라는 소리이고, 계산 과정이 32’000보다 작아야하는게 아니라서, 오히려 32’001보다 작을 때만 dp[i]에 삽입하는 것이 오류였음. (그래서 그 부분을 삭제)

생각해 볼 점

1. 큰 틀의 로직은 생각을 했는데, 계산 과정에서 32’000보다 큰 수가 들어갈 수 있다는 점을 놓쳐서 그것 때문에 너무 많은 시간을 허비한 것 같다. 항상 예외처리에 많은 시간을 투자하고 있는데, 어떨 때는 그게 불필요한 경우일 수도 있다는 걸 생각해봐야겠다.

해시태그

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL