https://programmers.co.kr/learn/courses/30/lessons/42895
-
flow
카테고리가 dp 인 문제이다.. solution[n] 을 N을 n번 사용했을 때, 만들어질 수 있는 모든 수라고 정의하면 solution[n+1] 은 solution[n] 집합 내 모든 수에서 N 을 사칙연산 해준 값이 되지 않을 까 생각했다. 바람직한 dp라고 생각되었지만
결과가 몇개 실패로 나왔다.. ㅋㅋ
고민 끝에 발견하게 된 건 문제 예시 중 5 두개를 사용해서 55를 만들 수 있다는 것..
솔직히 이거는 사칙연산이 아닌데?? ㅋㅋㅋㅋ (5 두개 이어 붙이는게 어떻게 사칙연산이냐..)
그러면 기존 솔루션은 당연히 예외가 발생한다. (55 + 55 같은 경우 실제 n=4 가 되지만 solution[3] 의 모든 원소와 N 간에 어떠한 사칙연산으로도 만들 수 없음.. )
결국 solution[i] 와 solution[j] 간의 사칙연산 모든 경우의 수로 solution[n] (n == i+j) 을 구성하는 함수를 만들어야 한다..
이미 dp에서 멀어진 것 같지만 일단 통과되긴 했다.
시간 복잡도는 문제에선 답이 8보다 커지면 멈추게 했지만 제한이 없이 m 이라 가정 하면..
O(nm^2) (n : solution[i] 의 평균 elements 갯수..) 가 될 것이다..
n 개의 operation을 각각 partial solution 만들기 위해 1,1,2,2,3,3,4,4... m/2 번이 필요
n (m/2)(m/2+1)/2 * 2 는 결국 O(nm^2)..
마음에 썩 들진 않지만 문제가.. 하여튼 결과는 아래와 같다.
python만 작성했는데 앞으로도 왠만하면 python 만 쓰는 것이 좋다고 생각이 된다.. 언어 여러개 하자니 속도도 느리고 기존 하던 js는 알고리즘 짜기에 속도가 너무 느린 것 같은 느낌이 들어 같은 솔루션도 후반에 가면 적용이 안될 것으로 예상.. -
result
https://github.com/songjy6565/alg-py/blob/master/programmers/level3/A1.py
