작업 저장소

Backjoon Online Judge 

"2579번 : 계단 오르기" 문제입니다.

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

문제에서 선택된 수의 최대값을 구하기 위해 DP를 이용하였습니다.

규칙 파악을 하기위해 k번째 계단을 올랐을때 최댓값을 구했습니다.

(k번째 계단의 점수를 s(k), k번째 계단의 점수의 합을 ms(k)로 표시합니다.)

1번째 계단까지 올라갔을 때 최댓값 : s(1)

2번째 계단까지 올라갔을 때 최댓값 : s(1)+s(2)

3번째 계단까지 올라갔을 때 최댓값 : max( [ s(1)+s(2) ] , [ s(2)+s(3) ] )

(1,2,3번째 계단을 모두 오를 수 없으므로)

이때 3번째 계단에 오르게 되는 경우의 수는

1. 이전 계단을 밟고 올라옴. [s(2)를 포함]

2. 이전 계단을 밟지 않고 올라옴. [s(2)를 포함하지 않음] 으로 나뉩니다.

1의 경우 이전 계단과 현재 계단을 밟으므로 2칸 아래 계단을 밟을 수 없고 3칸 아래 계단에서 최대 점수를 얻었을때 최대 점수를 얻을 수 있습니다.

2의 경우 이전 계단을 밟지 않았으므로 그 이전 계단까지 최대 점수를 얻으면 k번째 계단에서 최대 점수를 얻을 수 있습니다.

이를 일반화 해서 표현하면

k번째 계단까지 올라갔을 때 최댓값은

max( [ ms(n-3) + s(n-1) + s(n) ] , [ ms[n-2] + s(n) ] ) 이 됩니다.

아래는 코드 설명입니다.

 - 각 계단의 점수와 각 계단 위치에서 최댓값을 저장하기 위해 각각 score[Max]와 maxScore[Max] 배열을 선언했습니다.

 - 이후 maxScore[2]까지는 초기값으로 직접 값을 넣어주고 maxScore[3]부터는 위의 공식을 통해 계산하였습니다. 

코드는 C++로 작성하였습니다.

Backjoon Online Judge 

"1932번 : 숫자삼각형" 문제입니다.

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

일단 문제에서 선택된 수의 최대값을 구하기 위해 DP를 이용하였습니다.

 - 먼저 삼각형을 저장할 2차원 배열과 각각에 대해 최대값을 저장할 2차원 배열을 선언했습니다. (입력값을 받아오자 마자 배열에 쓰고, 저장되는 최대값을 덮어쓰는 방식으로 구현한다면 1차원 배열 2개로도 구현이 가능하리라 생각합니다.)

 - 이후 삼각형의 특성 상 양쪽 끝 부분은 더해지는 경우의 수가 하나이므로 이전 최대값을 불러와 더했고, 중간 부분은 이전 최대값 중 큰 값을 이용하였습니다.

코드는 C++로 작성하였습니다.

Backjoon Online Judge 

"1149번 : 피보나치 수 3" 문제입니다.

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

일단 문제에서 비용의 최솟값을 출력하기 위해 모든 선택 경우에서 나올 수 있는 비용을 알고 있어야 하고, 이를 구현하기 위해 DP를 이용하였습니다.

이때 문제의 조건을 만족하려면 현재 집을 칠해야 할 색은 이전집에 칠한 색깔이 아닌 색만을 칠할 수 있다는 사실을 확인했고 배열을 통해 검사하는 범위를 줄이기로 했습니다.

 - 먼저 N <= 1000이므로 모든 집의 색깔을 저장할 3*1000의 배열을 선언하여 그 배열에 저장하였습니다.

 - 이후 N에 따라 검사 결과를 저장할 total 배열에 비용의 최솟값을 저장했습니다. 이때 비용의 최솟값을 저장하기 위해 algorithm헤더에 포함된 min함수를 이용하였습니다.

 - 비용은 현재 집에 칠할 색깔 별로 비용을 각각 구했으며 비용은 이전 집에 칠한 색깔의 최솟값 중 현재 집에 칠할 색깔과 같지 않은 최솟값 중 작은것을 더했습니다.

코드는 C++로 작성하였습니다.

Backjoon Online Judge 

"1003번 : 피보나치 함수" 문제입니다.

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

피보나치 함수를 구할 때 특정 함수가 몇번 호출되었는지 알기 위해서는 피보나치 함수를 재귀적으로 구현하여 함수 호출 될 때 마다 함수 호출 횟수를 1씩 증가시키면 됩니다. 하지만 그렇게 구현 할 경우 시간이 오래 걸리기 때문에 점화식을 구하여 쉽고 빠르게 함수 호출 횟수를 구했습니다.

위 표를 보면 fibo(0)의 호출 횟수와 fibo(1)의 호출 횟수도 피보나치 수의 증가와 같이 증가하는 것을 알 수 있습니다. (N = 0일때는 제외)

fibo(0) : 0 1 1 2 3 ...

fibo(1) : 1 1 2 3 5 ...

따라서 피보나치수를 배열을 이용해 빠르게 구하고 N의 값에 따라 그에 맞는 피보나치 수를 fibo(0), fibo(1)의 출력값으로 이용했습니다.

 - fibo(0)의 호출 횟수는 N이 주어질때 fibo(N-1)과 같습니다.

 - fibo(1)의 호출 횟수는 N이 주어질때 fibo(N)과 같습니다.

(표를 보고 규칙을 유추)

코드는 C++로 작성하였습니다.

Backjoon Online Judge 

"2749번 : 피보나치 수 3" 문제입니다.

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

피보나치 수 3번의 경우 N의 범위가 매우 크기에 일반적인 방법으로 피보나치 수를 구할 경우 long long int에서 저장 가능 한 범위를 초과하기 때문에 제대로 된 답이 나오지 않습니다.

피보나치 수의 특징으로 피보나치 수를 나눈 나머지는 주기성을 띄게 됩니다.

(=피사노 주기) 이를 활용하여 문제를 풀어가게 됩니다.

피사노 주기에서 길이가 1,000,000 일 경우, 주기 Period는 1,500,000이 됩니다.

 - FIBO의 값을 일반적인 방식으로 구하되, 1,000,000이 넘는 경우 나머지만을 저장했습니다.

 - FIBO의 값이 주기에 해당하는 값을 넘는 경우 값은 순환하므로 더 이상 구하지 않았습니다.

 - n / 주기의 결과를 구해 n번째 값이 어느곳과 같은지를 확인하고 이를 출력했습니다.

코드는 C++로 작성하였습니다.