성장하고 싶은 신입 개발자

https://www.acmicpc.net/problem/14852

#include<iostream>
#include<stdio.h>

using namespace std;

int d[1000001];

int solution(int n){
    if(n == 0) return 1;
    if(n == 1) return 2;
    if(n == 2) return 7;
    if(d[n] != 0) return d[n];
    int result = 2 * solution(n-1) + 3 * solution(n-2);
    for(int i = 3; i <= n; i++){
        result += (2 * solution(n-i));
    }
    
    return d[n] = result % 1000000007 ;
}

int main(){
    int n;
    scanf("%d",&n);
    printf("%d",solution(n));
}

위 코드의 시간 복잡도

solution(n)을 구할 때 시간             =>   1(상수 시간)

뒤에 for문에서 sum을 구하는 과정   =>   n

solution()은 재귀 호출 함수이므로 총 n-1번 호출할 것이다. 그러므로 solution(n)을 구하는데 드는 시간은
1 * n 으로 n만큼 걸린다.

정리하면 solution()을 구할 때 시간 * 뒤에 for문에서 sum을 구하는 과정 = n * n  = O(n^2)

처음에는 위처럼 작성해서 제출했다. 하지만 시간 초과가 나왔다.

그 이유는 문제에서 N의 범위가 1~1,000,000 이었기 때문에 위의 코드로는 1000000^2 로 매우 큰 시간이 걸려서
시간 초과가 발생하기 때문이다.

그래서 sum을 구해주는 부분도 dp 테이블에 저장해서 매번 n번을 더하는 것이 아닌 더한 값을 dp 테이블에 저장
해두고 사용하도록 구현한다면 O(N)의 시간복잡도로 구현할 수 있다. 

즉, X[i] = sum( solution(i-1) + solution(i-2) + ... solution(0) ) 을 저장해 둔다면 그 다음 번에 X[i+1]을 구할 때는
저장되어 있는 값을 한 번 가져오기만 하면 도므로 O(1)만큼밖에 안 걸리기 때문이다. 그러므로 dp 이차원 배열을
이용해 구현하면 된다.

이게 바로 누적합을 저장해두는 누적합 문제 유형이다. ( 최적화를 필요로하는 심화된 dp 문제에 종종 나온다 )

정답 구현 

dp를 하나 더 만들어 sum을 저장해두자.

새로 만든 dp에 넣어야 할 값은 sum이다.

점화식

위 점화식에서 뒤에 2로 묶여있는 부분인 ( DP(n-3) + ... + DP(1) + DP(0) ) 를 새로 만든 dp에 넣어주는 것이 목표다.

실제로는 저 값을 2로 묶어줬으므로 DP[n][1]에 나중에 2를 곱해줘야 한다.

그러기 위해서 dp 이차원 배열을 만든다면

DP[n][0] => 길이가 2 x n일 때의 타일을 채우는 경우의 수가 들어감 

DP[n][1] =>  (solution(n-3) + ... + solution(1) + solution(0) ) 의 결과 sum 값이 들어감

위의 DP[n][1]을 다르게 보면 밑에처럼 볼 수 있다.

solution(n-3) + solution(n-2) + ... solution(0)
= { solution(n-3) } + { solution(n-2) + ... solution(0) }

즉, DP[n][1] = { DP[N-3][0] } + { DP[n-1][1] } 이 된다. 

그러므로
DP[n][1] = DP[n-3][0] + DP[n-1][1];

DP[n][0] = 3 * DP[n-2][0] + 2 * DP[n-1][0] + 2 * DP[n][1]; 

정답 코드     

#include<iostream>
#include<stdio.h>

using namespace std;

long dp[1000001][2];

long solution(int n){
    dp[0][0] = 1;
    dp[1][0] = 2;
    dp[2][0] = 7;
    dp[2][1] = 0;
    
    if(dp[n][0] != 0) return dp[n][0];
    
    for(int i = 3; i <= n; i++){
        dp[i][1] = (dp[i-3][0] + dp[i-1][1]) % 1000000007;
        dp[i][0] = (3 * dp[i-2][0] + 2 * dp[i-1][0] + 2 * dp[i][1]) % 1000000007;
    }

    return dp[n][0];
}

int main(){
    int n;
    scanf("%d",&n);
    printf("%ld",solution(n));
}

https://www.acmicpc.net/problem/11726

DP를 이용해 풀어야 하는 문제이다.

DP를 사용하기 위한 조건
   1. 큰 문제를 작은 문제로 나눌 수 있다.
   2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

위 조건에 부합하기 때문에 DP를 사용한다.
DP는 규칙을 찾아서 점화식을 세우는 것이 가장 중요하기 때문에 우선 규칙을 생각한다.

n-1, n-2 까지는 채워진 경우의 수가 구해진 상태라고 가정하자. 그 후 맨 뒤에 길이를 추가하면 될 수 있는 경우의
수는 2가지이다.

위와 같이 타일의 세로 길이가 n일 때 타일을 채우는 경우는 "2x1" 타일을 쓰는 경우, "1x2" 타일을 쓰는 경우
두가지이다. 그렇기 때문에 점화식은 다음과 같다.

D[i] = D[i - 1] + D[i - 2]

틀린 코드 ( overflow 문제 발생 )

#include <stdio.h>
#include <iostream>

using namespace std;

int d[1001];

int tile(int n){
  if(n == 1) return 1;
  if(n == 2) return 2;
  if(d[n] != 0) return d[n];
  
  d[n] = tile(n-1) + tile(n-2);
  return d[n];
}

int main(){
  int n;
  scanf("%d",&n);
  printf("%d",tile(n) % 10007);
}

처음에 위와 같이 코드를 구현했더니 계속 틀렸습니다라고 나와서 당황스러웠다.
사실 틀렸습니다가 나온 이유는 재귀 호출해서 값을 계속 더하는 문제는 값이 매우 커지는 경우가 많기 때문에
OverFlow문제를 야기할 수가 있다.

=> 즉, 문제에서 10007로 나누라던 이유도 값이 매우 커져서 int값을 넘어가 overflow가 발생하는 경우를 방지하기
     위함이다. 그러므로 tile 함수 안에서 10007을 나눈 나머지를 배열에 저장하도록 구현해야 overflow가 나지 않고
     문제를 해결할 수 있다.

문제)

다솜이는 기타를 많이 가지고 있다. 그리고 각각의 기타는 모두 다른 시리얼 번호를 가지고 있다. 다솜이는 기타를 빨리 찾아서 빨리 사람들에게 연주해주기 위해서 기타를 시리얼 번호 순서대로 정렬하고자 한다.

모든 시리얼 번호는 알파벳 대문자 (A-Z)와 숫자 (0-9)로 이루어져 있다.

시리얼번호 A가 시리얼번호 B의 앞에 오는 경우는 다음과 같다.

1. A와 B의 길이가 다르면, 짧은 것이 먼저 온다.
2. 만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다)
3. 만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다.

시리얼이 주어졌을 때, 정렬해서 출력하는 프로그램을 작성하시오.

어려웠던 점)

- string 배열에 시리얼 번호들을 저장했는데 저장된 시리얼 번호에서 숫자일 때만 골라서 그 숫자들의 합을 구하는
  부분이 시간이 조금 걸렸다.

해결 방법)

- 문자는 아스키 코드이므로 문자가  '0' 과 '9' 사이일 때만 숫자이다. 그렇게 조건을 걸고 그 조건에 성립한다면
  숫자이기 때문에 그 값을 sum 변수에 더해준다. 이 때 string 변수의 안에 있는 숫자('9' 같은 문자)들을 더한 총합을
  구하려면 각 숫자에 해당하는 만큼 sum변수에 더해줘야 하는데 이 방법은 a[i] - '0' 으로 하면 아스키코드 값의 차이
  만큼이 그 숫자를 의미하게 되므로 이 값을 더해주면 된다.