이친수
- boj.kr/2193
- 이진수에서 특별한 속성이 추가됨
1. 0으로 시작하지 않는다.
- 1이 두번 연속으로 나타나지 않는다.
- 이를테면 1, 10, 100, 101, 1000, 1001이 이친수
- 0010101이나 101101은 각각 1,2 번 규칙에 위배되므로 이친수가 아니다.
- 케이스 분할
- n번째 자리에 0이 온 경우
- n번째 자리에 1이 온 경우
- 확실한 것들은 fix시키고 유동적인 것들만 보는 능력이 필요
- ex) n=4일때
1. 앞의 10은 무조건 고정
2. 맨 뒤의 숫자는 0 또는 1만 가능하다.
3. 가운데 올 수 있는 숫자는?
3. 1. 맨 뒤가 0일 때 0과 1 둘 다 가능
3. 2. 맨 뒤가 1일 때는 0만 가능
- 케이스 분할을 이용하여 올 수 있는 숫자를 제한하고 쉽게 풀 수 있다.
- 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
public class Main{
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
BigInteger[] d = new BigInteger[91];
d[1] = new BigInteger("1");
d[2] = new BigInteger("1");
d[3] = new BigInteger("2");
d[4] = new BigInteger("3");
d[5] = new BigInteger("5");
for(int i=6; i<=n; i++){
d[i] = (d[i-1].add(d[i-2]));
}
System.out.println(d[n]);
}
}
쉬운 계단 수
- 이친 수와 비슷
- 인접한 모든 자리수의 차이가 1이 남
- ex) 456456
- 길이가 N인 계단 수의 개수는?
- 접근법
- 이친수와 마찬가지로 끝에 L이 온다고 가정하고 풀면 쉽다.
- D[N][L]처럼 2차원 배열을 만든다. N은 자리수의 개수고 L은 끝에 오는 숫자이다.
- D[3][2]는 3자리수일 때, 끝이 2로 끝나는 계단 수의 갯수이다.
- 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
long[][] d = new long[101][101];
int mod = 1000000000;
for (int i = 1; i <= 9; i++)
d[1][i] = 1;
for(int i=2; i<=n; i++) {
for (int j=0; j<=9; j++) {
if(j-1 < 0) d[i][j] = d[i-1][j+1];
else d[i][j] = d[i-1][j-1] + d[i-1][j+1];
d[i][j] %= mod;
}
}
long sum = 0;
for (int i = 0; i <= 9; i++)
sum += d[n][i];
System.out.println(sum % mod);
}
}
오르막 수
- boj.kr/11057
- 수의 자리가 오름차순을 이루는 수
- 인접한 수가 같아도 오름차순으로 친다.
- 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 문제
- 수는 0으로 시작할 수 있다.
- ex) 123345, 357, 88888888, 15559999
- 문제 해결 포인트
- N=2부터 숫자가 1증가할 때마다 올 수 있는 숫자의 범위를 잘 계산하면 된다.
- 간단하게 생각했을 때, N=2일 때, D[N][1] = D[N][0] + D[N][1] 인 것을 알면 된다.
- 1로 끝나는 2자리 수는 01 11 여기서 1 앞에 붙는 0 1은 이전 배열에서 참조하면 된다.
- 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
public class Main{
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
BigInteger[][] d = new BigInteger[1001][1001];
for(int i=1; i<=2; i++){
for(int j=0; j<=9; j++){
if( i == 1) d[i][j] = new BigInteger("1");
if( i == 2) d[i][j] = new BigInteger(Integer.toString(j+1));
}
}
for(int i=3; i<=n; i++){
for(int j=0; j<=9; j++){
d[i][j] = new BigInteger("0");
for(int k=0; k<=j; k++){
d[i][j] = d[i][j].add(d[i-1][k]);
}
}
}
BigInteger sum = new BigInteger("0");
for(int i=0; i<=9; i++)
sum = sum.add(d[n][i]);
System.out.println(sum.mod(new BigInteger("10007")));
}
}
스티커
- boj.kr/9465
- 조건
- 스티커 2n개가 2Xn모양으로 배치되어 있다.
- 스티커 한 장을 떼면 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없다.
- 점수의 최대 합을 구하는 문제
- 전략
- 가장 큰 숫자를 떼는 것이 옳은가?
- 아니다. 주변의 숫자들이 아주 근소한 차로 큰 숫자들로 이루어져있다면 오히려 손해.
- 스티커를 떼는 임의의 순서를 정하자
- 왼쪽에서 오른쪽으로 위 아래 스티커를 뗄지 말지 결정한다고 가정하자.
- 케이스별로 나눠서 풀자.
- 0번 위 아래 모두 안 떼는 것 (XX)
- 1번 위 떼고 아래는 안 떼는 것 (OX)
- 2번 위 안 떼고 아래는 떼는 것 (XO)
- 매 루프마다 어떤 연산을 수행해야 할까?
- 위에 정의한 0, 1, 2번 케이스에 대한 최대 값을 3개의 배열에 각각 넣어야 한다.
- 0번 케이스의 경우
- 이전 케이스로 0, 1, 2번 모두 올 수 있음
- max(d[i-1][0], d[i-1][1], d[i-1][2])
- 1번 케이스의 경우
- 이전 케이스로 0, 2번 올 수 있음
- 그리고 자신의 스티커 점수도 합산해줘야 함
- max(d[i-1][0], d[i-1][2]) + 스티커[i][1]
- 2번 케이스의 경우
- 1번과 비슷
- max(d[i-1][0], d[i-1][1]) + 스티커[i][2]
- 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for(int i=0; i<t; i++) {
int n = Integer.parseInt(br.readLine());
int[][] stickers = new int[n][3];
int[][] d = new int[n][3];
StringTokenizer st0 = new StringTokenizer(br.readLine(), " ");
StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
for(int j=0; j<n; j++){
stickers[j][1] = Integer.parseInt(st0.nextToken());
stickers[j][2] = Integer.parseInt(st1.nextToken());
}
d[0][0] = 0;
d[0][1] = stickers[0][1];
d[0][2] = stickers[0][2];
for(int j=1; j<n; j++){
d[j][0] = Math.max(Math.max(d[j-1][0], d[j-1][1]), d[j-1][2]);
d[j][1] = Math.max(d[j-1][0], d[j-1][2]) + stickers[j][1];
d[j][2] = Math.max(d[j-1][0], d[j-1][1]) + stickers[j][2];
}
sb.append(Math.max(Math.max(d[n-1][0], d[n-1][1]), d[n-1][2]) + "\n");
}
System.out.print(sb.toString());
}
}
포도주 시식
- boj.kr/2156
- 조건
- 1부터 n까지의 포도주가 테이블 위에 순서대로 놓여있고 각 포도주의 양은 다를 수 있다.
- 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치로 놓아야 한다.
- 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
- 최대한 많은 양의 포도주를 맛봤을 때 그 합은?
- ex) 6개의 포도주 잔이 있고 각각의 잔에 6, 10, 13, 9, 8, 1만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.
- 전략
- 케이스별 분리
- 안 마신 상태일 때
- 이전 상태로 아무거나 올 수 있음
- max(이전에 안마심, 이전에 1잔, 이전에 2잔)
- 1잔 마신 상태일 때
- 이전에 안마심 + 이번 잔의 양
- 2잔 마신 상태일 때
- 이 전에 1잔 마심 + 이번 잔의 양
- 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] podojus = new int[n];
int[][] d = new int[n][3];
for(int i=0; i<n; i++){
podojus[i] = Integer.parseInt(br.readLine());
}
d[0][0] = 0;
d[0][1] = podojus[0];
d[0][2] = podojus[0];
for(int i=1; i<n; i++){
d[i][0] = Math.max(Math.max(d[i-1][0], d[i-1][1]), d[i-1][2]);
d[i][1] = d[i-1][0] + podojus[i];
d[i][2] = d[i-1][1] + podojus[i];
}
System.out.println(Math.max(Math.max(d[n-1][0], d[n-1][1]), d[n-1][2]));
}
}