알고리즘을 좋아하는 나

dp로 풀었다. O(NM)

입력차례대로 위칸과 왼쪽칸과 왼쪽위 대각선 칸을 비교해서 가장 작은값 + 1로 새로운 정사각형을 만들 수 있다.

동전 문제와 비슷한 풀이다.

tetrahedron에 먼저 사면체에 필요한 폭탄들의 개수를 넣어준다.

그리고 동전 문제처럼 minimumQuantity[tetrahedron[i]] = 1을 해주고,

계산한다.

동전 문제 풀이와 약간 다른점은 동전문제는 나누고나서 뭐 쭉 했다면,

이건 시간초과가 나서  minimumQuantity[i]를 구할 때, minimumQuantity[minimumQuantity[i - tetrahedron[j]] + 1 이런식으로 구했다.

동전문제도 이렇게 변경해서 풀 수 있을거 같다.

coinList[i]에는 i를 만들기위한 최소 동전 개수가 들어간다.

Bottom-Up 방식

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에 있는 규칙이 보인다.

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

순서도 상관없다.

하지만 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] 에 최댓값이 들어간다.

k-1층의 1~b호 까지의 사람들이 k층 b호에 살아야 된다.

0층 i호에는 i명이 산다.

배열이

1 2 3 4 5

1 3 6 10 15

이런식으로 만들어진다.

위에서 부터 0층 1층 으로 계산했을때

d[i][j] = d[i-1][j] + d[i][j-1] 이다.

그래서 처음 입력받기 전에 초기화해주고 

입력받는 값으로 배열에 대입해서 출력하면 된다.

증명 블로그

https://rkm0959.wordpress.com/2017/03/17/inequality-for-the-minimum-number-of-squares-to-partition-a-rectangle/

스터디에서 순열과 조합을 공부한다.(순열은 아직 뭔지 모름)

조합 문제를 풀었다.

분자식이 나오는데, 분자식이 어떤건지 몰라서 도움을 많이 받았다.

문제는 M1 + M2 = M3 가 균형이 맞으면 된다.

원자번호로 균형을 맞추는게 아니라 각 원자의 갯수를 맞춰야 된다.

아이디어만 있으면 쉽게 풀 수 있는 문제.