알고리즘/프로그래머스 썸네일형 리스트형 [Lev.3] 자물쇠와 열쇠(C++) 1. 문제 2. 접근 방법 1. 문제 조건 보면서 범위 줄여가기 1) 모든 홈이 다 차야 한다 => 홈이 발생한 구역을 구한다. 만약 열쇠 사이즈가 홈 구역보다 작으면 false return(경우의 수가 아예 안만들어 진다.) 2) 자물쇠의 돌기와 열쇠의 돌기가 맞닿으면 안된다 => 홈이 아닌 부분은 무조건 돌기이다 => 자물쇠의 홈 구역 밖으로 열쇠의 돌기가 있는 경우는 열 수 없음 3) 자물소의 홈 모양 전체와 열쇠의 돌기 모양 일부가 일치해야 한다. -> 나는 처음에 이렇게 접근했었는데, 이렇게 좁은 범위나 예외 케이스부터 생각하지 말고 큰 관점에서 먼저 생각하는 연습을 하자. 2. 가장 간단한 방법부터 생각하기 1) 모든 경우에 대해서 열쇠를 돌려가면서 맞춰본다 -> 완탐 -> 범위를 보니 가능한.. 더보기 N으로 표현(DP) / C++ 1. 문제 2. 접근 방법 1) 문제 조건, 제한 범위 찾기 - N은 최대 8번 사용 가능하다 => 연산을 수행할 수는 N~NNNNNNNN까지 가능 - 괄호 사용 가능 2) DFS로 풀기 2-1) 종료 조건 : 원하는 수를 찾았을 때, cnt가 8을 넘어갔을 때 2-2) 재귀 함수 호출 : 0부터 시작, 현재 수에 N부터 NNNNNN까지 사칙 연산을 각각 수행하면서 재귀함수를 호출한다. => 현재 수 (+ / - / * / 나눗셈) N,NN,NNN,...,NNNNNN 2-3) 효율적으로 짜는 법 : - 현재 수가 0인 경우엔 곱셈 나눗셈 수행 안함 - 2-2)에서 현재 수에 연산할 N의 범위는 최대 NNNNNN이다. (for문은 N부터 NNNNNN까지 6번 수행) NNNNNNN과 NNNNNNNN이 안되는.. 더보기 이전 1 2 3 다음
