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

풀이

1. d[i]

1

i번째 까지 해석했을 때, 경우의 수

2. i번째 문자

• 한 자리로 해석되는 경우 : 1 ~ 9
• 두 자리로 해석되는 경우 : 10 ~ 26

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

풀이

1. d[i]

• 3 * i 타일을 채우는 방법의 수

2. 가장 마지막에 올 수 있는 경우를 찾아야 한다.

1

d[i] = 3 * d[i-2]

1

d[i] = 2 * d[i-4]

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

틀린 풀이

1. d[i] = i의 제곱수의 항의 최소 개수

2. n과 가장 가까운 제곱수를 찾음

3. d[n-(n과 가장 가까운수의 제곱수)] + 1

4. +1을 하는 이유

   • 제곱수 자체도 하나 이기 때문에

5. 예를 들어

   • d[7] = d[ 7 - 2^2 ] + 1 = d[3] + 1 이라고 생각했다

6. 하지만, 위의 예시에서, d[3]이 가장 작은 값이라는 보장이 없다

7. 즉, 가장 가까운 제곱수를 찾는 것이 틀림

맞는 풀이

1. 예를 들어 ,

   • d[25] 를 구하려고 할때,
   • d[25-1^2] + 1
   • d[25-2^2] + 1
   • d[25-3^2] + 1
   • d[25-4^2] + 1

2. min 값이 답

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

풀이

1. d[i]

   • a[i]를 밟았을 경우, 0~i 번째까지 최대 점수

2. d[i]

   • max( a[i]+a[i-1]+d[i-3] , a[i]+d[i-2] )

3. example : 10 20 15 25 10 20

   • 20 X 15 O 25 O : a[i]+a[i-1]+d[i-3]
   • 15 X 25 O : a[i]+d[i-2]

4. 근데, 여기서 사소한 문제 !

   • n을 입력받고, 배열을 생성할 때
     0n-1 인덱스로 할 것이냐,
     1n 인덱스로 할 것이냐에 따라 문제가 생김

5. 0~n-1 인덱스로 다음과 같이 하면 틀렸음.

   • 왜냐하면, d[2]를 구하지 않았기 때문.

6. 따라서 다음과 같이 d[2]를 구해야함

7. 1~n 인덱스로 범위 잡으면, 상관 없음

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

풀이

1. d[n]
   a[n]을 마지막으로 하는 연속하는 수들의 합 중 가장 큰 수

2. 예를들어,
   10 -4 3 1 5 6 -35 12 21 -1

3. d[4]

   • 5
   • 5 + 1
   • 5 + 1 + 3
   • 5 + 1 + 3 -1
   • 5 + 1 + 3 -1 -4
   • 5 + 1 + 3 -1 -4 + 10
   • 중 가장 큰 값

4. 여기서 dp 문제라고 파악해야함

5. 왜냐하면,

6. d[3] 은

   • 1
   • 1 + 3
   • 1 + 3 - 4
   • 1 + 3 - 4 + 10
   • 이기 때문이다.
   • d[3]이 d[4] 구할때 쓰임

7. 따라서
   d[4] = max ( a[4] , a[4]+d[3] )

8. 즉,
   d[n] = max ( a[n], a[n]+d[n-1] )

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

풀이

1. 가장 긴 증가하는 부분 수열 문제와 가장 긴 감소하는 부분 수열 문제를 더한 문제

2. 가장 긴 증가하는 부분 수열을 구한다

3. 가장 긴 감소하는 부분 수열을 구한다

4. d1[i] + d2[i] -1 의 최대값을 구한다

5. 여기서 1을 빼는 이유 => 증가하다가 감소할 경우에 1이 두번 더해지기 때문에

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

틀린 풀이

• a 진법 -> 10진법 -> b진법
• 다음과 같이 풀면 틀렸다고 나옴.

맞는 풀이

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

풀이

1. 일반적인 진법 변환이랑 같음

2. -2로 계속 나누어감

3. 양수냐 음수냐가 중요

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

풀이

1. 몇 번 나누는지 count

2. count 만큼 배열 생성

3. 생성한 배열에 n%b를 차례대로 저장

4. n 은 n/b를 새로 저장

5. n이 0보다 클때까지 3번4번을 반복 실행

6. 값들을 저장한 배열의 값을 index 끝부터 0까지 차례대로 출력

7. 그런데, 해당 index의 값이 10보다 큰경우는

8. char(값+55) 로 출력

1
2
3
4
5
6
7
8
9
10
11
12

StringBuilder ans = new StringBuilder();
        while (n > 0) {
            int r = n % b;
            if (r < 10) {
                ans.append((char)(r + '0'));
            } else {
                ans.append((char)(r - 10 + 'A'));
            }
            n /= b;
        }
        System.out.println(ans.reverse());
    }

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

틀린 풀이

1. 수학에서 진법 변확 하는 방식으로 풀면 됨

2. 수는 string 으로 , 진법은 int 로 입력 받음
   (string으로 받아 각 자리에 접근하고, 자릿수를 쉽게 파악하기 위해)

3. 각 자리 수에 접근하여 int로 입력받은 수의 자릿수 제곱을 곱하여

4. 더함

맞는 풀이