키큰개발자

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

해결 방법 :

이 문제는 다이나믹 프로그래밍 문제다.

그렇기 때문에 먼저,

우리가 구하고자 하는 문제가 뭔지 본다. 

문제는 주어진 자연수 N을 제곱수들의 합으로 표현할 때에 그 항의 최소개수 이다. 

ex) N = 3  , 1^2 + 1^2 + 1^2 = 3개 

    N = 7,  3^2 + 1^2 + 1^2 = 3개

나는 처음에 접근한 방법이 제곱을 했을때 (N 과 가장 가까운 수에 대해 최소항의 개수  + N- 가장가까운수 에대한 최소항의 개수) 로 점화식을 세워서 풀었었다. 하지만 이는 12를 구할때 깨져버린다. 

위점화식을 적용해보면, 9의 최소항의개수 + 12-9의 최소항의개수 = 4가 나오게 된다.

2^2 + 2^2 + 2^2 = 3개 이것이 최소개수인데 말이다. ㅜㅜ

다시 생각해 본 후 , 모든 경우를 고려하면 답을 구할수 있다고 봣다.

즉, 어떤 수 12는  제곱의 합에서 1의 제곱이 포함됬다고 보면 11의 최소항의개수 + 1 이 될것이다. 여기서 +1 은 1의 제곱이 포함됬기 때문이다.

12는 또 제곱의 합에서 2의제곱이 포함됬다고 보면 10의 최소항의 개수 + 1 이 된다.

12는 또 제곱의 합에서 3의 제곱이 포함됬다고 보면 9의 최소항의 개수 + 1이 된다.

이렇게 모든 경우를 포함하는 점화식을 세운다면 DP[N] = MIN ( DP[N], DP[N-j의제곱] + 1)  이될것이다.

(이때, j는 제곱해서 N보다 같거나 작을때까지의 수를 반복해서 도는 경우이다.)

문제 링크 : 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] 를 각각 구해서 최소값을 찾으면 답을 구할 수 있다.

소스코드)

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

해결방법 : 

1 부터  N까지 -, +, " " 의 연산을 사이에 각각 넣어서 최종 합이 0이 되는 식을 모두 출력하는 문제다.

일단 식을 누적하는 변수 str, 최종합을 누적하는 변수 sum을 설정하고 생각해봤다.

자연스레 3가지경우에 대해 재귀호출을 하면 모든 경우를 만들 수 있기에 3가지의 재귀함수를 설계하면 답을 구할 수 있다.

여기서 ""연산에 대해 주의할 점이 있는데, 

다음 재귀에 +나 -를 만나면 이전의 값(num)을 sum에 더해주거나 빼준다. 그전에는 sum에 아무런 계산하지 않는다.

이말은 ""로 된부분은 num에 합쳐진숫자로 업데이트만 하고, 다음에 +나-가 오면 계산을 해준다는 것이다.

나머지 -, +의 경우에는 다음에도 -,+일때 sum에 num*sign 값을 더해준다. 참고로 sign을 곱해주고 더해주면서 뺄셈을 한다. 

재귀함수로 넘겨주는 값을 보면 이해가 될것이다.

소스코드)

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

해결 방법 :

피보나치 함수를 재귀함수, Top-down 방식으로 푼다고 했을 때 fibonacci(0), fibonacci(1) 의 호출 개수를 각각 출력하는 문제다.

처음에는 단순히 

if(n == 0) 일때 0의 카운트 증가,

if(n == 1) 일때 1의 카운트 증가로 바로 풀수가 있었는데 채점해보니 시간초과가 떴다.. ㅋ

아 그러면 익히알고있는 다이나믹프로그래밍으로 메모를 쓰고 읽어서 시간을 줄여야 되는 구나라고 생각했다.

테스트 케이스를 가지고 여러번 하다보니 다음과 같은 규칙을 발견했다.

N의 0호출 개수는 N-1의 1호출 개수라는 것

example)  5의 0의 호출개수 = 4의 1의 호출개수, 다른것도 직접해보면 알것이다.

따라서 N과 N-1의 피보나치함수를 호출하고 N==1일때 1의 카운팅을 리턴하여서 각각 총 1의 호출개수를 각각 구할 수 있었다. 

이때, 재귀함수에서 여러 N의 1의호출개수를 메모로 저장해둬서(d[N]) 시간을 줄였다.

소스코드)

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

해결 방법 :

문제를 보면 각 자리 숫자가 등차수열을 이루는 것을 한수라고 했다.

testcase를 보고 처음에 조금 이상했는데 그 이유는 1,2,3,4,5,6과 같은 숫자도 등차수열로 카운팅 됫다는 점이다. 

일의자리숫자들은 등차라는 것이 없는 것인데.. 무튼 0의 등차가 있다라고 생각하고 이것만 예외로 생각하고 나면

간단하게 나머지 숫자들은 자리수를 각각 추출해서 등차가 같은지만 확인해서 카운팅 해주면 한수의 수를 구할 수 있다.

(참고)백의자리수 - 십의자리 == 십의자리 - 일의자리 

소스코드)

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

해결방법 :

문제에서 주어진 규칙대로 새로운 수를 만들기위해 몇번 반복 하는지를 세어주면 답이다.

1. 새로운 수를 십의자리와 일의 자리로 나눈다.

2. 나눈 수를 더한다. (십의자리숫자 + 일의자리숫자) 

3. 1번에서 구한 일의 자리와 2번에서 구한 수의 일의 자리 값을 붙인다. 즉 새로운 수를 구한다.

   (붙인다는 것은 1번의 일의자리를 10의자리로 만들기위해 * 10 한 후  2번에서 구한 일의자리를 그대로 더하면 된다.)

4. 1~3번을 반복한다. 새로운수가 처음 주어진 수와 같을 때까지!  

이때, 싸이클 횟수가 답이기 때문에 반복 할때마다 카운트를 하나씩 증가해준다.

소스코드)

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

해결방법 : 

삼각형 형태를 보면은 똑같은 부분이 3개위치에서 반복해서 그려지는 것을 볼 수 있었다.

맨위의 꼭짓점기준 1개 (하나의 삼각형 모습을 보이고 있다.)

맨위에서 왼쪽 아래에 있는 꼭지점 상단 1개 (하나의 삼각형 모습을 보이고 있다.)

맨위에서부터 오른쪽 아래에 있는 꼭지점 상단 1개 (하나의 삼각형 모습을 보이고 있다.)

이때 최소 단위의 형태는 3개의 높이의 별 삼각형 모습이고 이것을 기저조건으로 세운 후 높이가 3이되면 별을 찍어준다.

그리고 위에서 나눈 3개의 기준 좌표를 재귀함수로 넘기면서 각위치 마다 삼각형을 전부 그려준다.

따라서 재귀함수를 전부 돌면서 최소단위인 별 삼각형을 전부 찍어주면서 재귀가 끝난후 출력해주면 답을 구할 수 있다.

소스코드)

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

해결방법 :

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

문제의 조건 그대로 알고리즘을 설계하면 답을 구할 수 있다.

맨앞에 요소보다 뒤에 큰값이 없다면 그대로 queue에서 제거하면서 빼낸다.

아니라면 queue에서 맨앞에 요소를 뒤로 옮겨준다.

이걸 구현하기 위해서 앞에 추가삭제, 뒤에 추가삭제가 용이한 STL의 dequeue 자료구조를 사용했다.

그리고 찾고자 하는 문서정보를 가지고 있어야하기에 pair도 사용하였다. (second 요소 : 원래 주어진 인덱스위치)

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

해결방법 : 

보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 

이 문제에서 주어진 설명을 보면 하루마다 익은 토마토 좌표를 기준으로 인접한 네 방향에 안익은 토마토를 익게하므로 BFS탐색 방법을 사용하기로 생각했다. 테스트케이스에서 익은 토마토를 기준으로 따라 그려나가다 보면 이해하기 쉬울 것이다.

따라서 상자에 있는 토마토 모두가 익는데 최소의 일수는 BFS 탐색을 하고난 후의 최종적인 depth(깊이) 값이다. (그림참고)

프로그램 로직은 크게 bfs 탐색 전후로 나눌수있는데,

탐색 전에서는 입력을 받는 가운데 map에서 -1값을 갖고있으면 해당 좌표를 방문처리를 미리 해버렸다.그리고 1값을 가진 토마토 익은 기준좌표를 queue에 넣고 이좌표 또한 방문 처리를 해준다. 그리고 한번 전체를 탐색해서 이미 다 익었는지를 확인하고 다익었으면 0을 출력하고 아니면 bfs 탐색을 시작하게 했다.

bfs를 탐색한 후에는 visit배열을 보고 0이 하나라도 남아있다면 -1 출력하고 아니라면 bfs탐색에서 구한 depth값을 출력했다.

소스코드)