키큰개발자

문제 링크 : https://www.acmicpc.net/problem/1932

해결 방법 :

제일 단순하게 처음 시도했던 방법은 완전탐색으로 왼쪽합누적, 오른쪽 합누적 하는 방법으로 n번째 줄까지 전부 구했었다.

그리고 n번째줄에서 모든 합들을 비교해서 최대값을 찾아서 출력했었는데, 시간초과로 틀렸었다. 알고보니 2의 n승의 시간복잡도....ㅜ

그래서 다이나믹프로그래밍의 메모이제이션 기법을 사용해야겠다는 생각을 했다. 왜냐 시간초과니까 ㅜ

시간을 줄일방법을 생각해보니까 재귀를 줄여야겠다고 생각했다.

재귀를 줄이려면 각각의 요소가 최대값을 가져야했고 그거를 재호출했을때 미리 저장해놓은 최대값을 툭 내뱉어버리면 다시 재귀호출을 안할수 있다고 생각했다.

그래서 n번째 줄에서 부터 거꾸로 찾아나갔다. (top-down 방식)

n번째줄의 i번째 요소까지의 최대값은 max(n-1번째줄의 i번째 최대값, n-1번째줄의 i-1번쨰 최대값) + n번쨰줄의 i번째요소값 의 점화식으로 구할 수 있었다.

그리고 이를 기록해야한다. 왜? 재호출 방지위해서

식으로보면, d[x][y] = max(solve(x-1,y), solve(x-1,y-1)) + a[x][y] 이다.

또한, -1은 범위밖에있는 것들을 미리 저장해놔서 그곳에 호출하려하면 0을 리턴한다.  왜냐? 존재하지 않는 값이니까..

문제링크 : https://www.acmicpc.net/problem/1149

해결방법 :

RGB 거리의 모든 집들을 R,G,B 색으로 칠했을때 드는 최소비용을 구하는 문제인데, 나는 제일 마지막집을 때내어 생각했다. 

제일 마지막 집이 빨간색으로 칠해질 때 이웃한 집은 G, B 두가지중 하나로만 색칠해야된다.

마찬가지로 그린 이라면 이웃한 집은 R,B 두가지 중 하나로 칠해져야한다.

즉, 하나의 색깔이 정해지면 이웃한집은 그에 따라 두가지의 경우로 나눠진다.

위의 컨셉을 이용해서 점화식을 세워보면 다음과 같이 만들 수 있다.

D[N][0] = N번째 집이 빨간색으로 칠할 때,  모든 집의 최소비용 으로 정의한다. (0 : 레드, 1 : 그린, 2: 블루)

그러면 D[N][0] = min(D[N-1][1], D[N-1][2]) + rgb[N][0]  의 점화식을 세울 수 있다.

마지막집이 r,g,b 세가지의 경우를 가지기 때문에 D[N][0], D[N][1], D[N][2] 를 각각 구해서 최소값을 찾으면 답을 구할 수 있다.

소스코드)

면접을 보면서 나에 대해 조금 알았던 점이 있다.

긴장한나머지 빨리 질문을 받고 답을해야겠다는 심리가 잡혀있다.

그래서 질문에 대한 답을 할수 있는데도 불구하고 엉뚱한 답을 내는 경우가 종종 발생했다.

오늘 어떤 영어 관련질문이 들어왔는데 당장에 답을 내는게 안됬었다. 

그렇다면 한글로라도 떠올려서 말을 했었어야했는데.. 평소에 알고있고 문제도 풀었는데...

한글을 먼저 떠올릴수 있었다면 영어도 당연히 생각났었을텐데 ,,, 아쉬웠다 ㅜㅜ 

그래도 면접에 솔직히 임하자라는 건 지켯어서 조금은 만족하지만 이제는 조금 침착히 면접에 임하는걸 해봐야겠다.

ps. 잡플래닛에 코딩테스트 본다고해서 이걸로라도 잘봐서 공백기에 공부를 했다는 걸 보여주고 싶었는데... 시험을 전혀 보지 않았다..

     잡플래닛을 모두 믿지말자ㅜ ㅋㅋ