알고리즘을 좋아하는 나

에라토스테네스의 체의 방법을 사용하는데, 소수를 구하는게 목적이 아니고 K 번째 지워지는 숫자를 구하는게 목적

1 1 1 1    모

1 1 1 0    도

1 1 0 0    개

1 0 0 0    걸

0 0 0 0    윷

1이 나올때마다 count에 --해줘서 character형 배열에서 뽑아 쓰는식으로 했다.

0! = 1

팩토리얼 구하는 문제.

N은 약수의 처음 주어진 숫자와 마지막 숫자를 곱해주면 나온다.

예를 들어 9가 N이면

3 이 약수로 있다.

그러면 3 * 3 = 9

20 이면

2 4 5 10

2 * 10 = 20 

20 은 2 * 2 * 5 로 소인수 분해가 된다.

2 와 10

2 x 2 사이즈의 초콜릿은

1 x 2

1 x 2 로 나눠진다.

3 x 3 사이즈의 초콜릿은

1 x 3

2 x 3 이런식으로 나눠진다.

1 x 3 은 

2번 자를 수 있다.

코드가 더럽다.

종이에

• 1
• 1
• 2
• 1 1
• 2
• 3
• 1 1 1
• 1 2
• 4
• 1 1 1 1
• 1 1 2
• 2 2
• 5
• 1 1 1 1 1
• 1 1 1 2
• 1 2 2
• 5
• 6
• 1 1 1 1 1 1
• 1 1 2 2
• 1 1 1 1 2
• 2 2 2
• 1 5

규칙이 보이십니까?

k가 6인것으로 예를 들어보면, 

1 1 1 1 1 1 을 넣고

4에 있는 규칙이 보인다.

1. BFS

2. 방문했으면 --를 안함

계단 문제와 다르게 마지막것을 출력하는게 조건이 아니다.

순서도 상관없다.

하지만 3개이상은 연속으로 안된다.

규칙은

이것중에 max를 찾아서 넣으면 된다.

• i-3의 합 + i-1 포도주 양 +  i의 포도주 양
• i-2의 합 + i의 양
• i-1의 합

i-1의 합은 이전의 것들이 연속으로 2잔을 먹었을 때, 현재것은 못먹는것 체크하기 위함.

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

밑에서 위로 올라오면서 계산하면 [0][0] 에 최댓값이 들어간다.