알고리즘을 좋아하는 나

1 1

2 1 1

3 1 1 1

4 1 2 1

5 1 1 2 1

6 1 2 2 1

7 1 1 2 2 1

이동 거리는 이런식으로 된다.

idx    이동횟수

1         1

2        2

3        3

5        4

7        5

y에 이동해야 되는 거리를 넣어두고

pos에 현재 위치를 담았다.

처음에는 무조건 1을 이동해야 돼서 초기값이 1이다.

while loop을 돌때 i++/2를 해준 이유는 

9를 예로들면

1 2 3 2 1 인데

pos의 값이

1

while loop 시작

2

3

5

7

10

끝

이다.

i의 값을 구하면 5다.

결론적으로는

1 2 3 2 1

인것을

1 1 2 2 3 로 하는거다.

3을 예로들면

1 2 3 이 된다.

1 1 1 ㅇㅇ

끝.

다른 블로그를 많이 참고했다.

증명 블로그

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

3개의 풀이가 나왔다.

1. 시간초과

하나씩 다 더해줌

2. 런타임

2차원 배열을 만들어서 무게별로 나누고 또 거기에서 컬러별로 나눴음

2000 * 2e5 * 4 = 1G가 넘어가서 런타임 에러

3. 정답

블로그를 조금 참고했지만, 짜고나니 거의 똑같게 나옴...

total 스코어 idea를 참고함.

간단하게 N으로 받고 숫자마다 체크해서 더해줬다.

음 펜윅트리를 공부하기 위해 풀었다.

펜윅트리의 원리는 이해가 됐다.

그런데 idx에 m만큼 더해준 아이디어는 다른 블로그들을 참고했다.

BOJ 3653 풀이를 검색하면 나오는 블로그를 거의 본 것 같다.

음.. 내 것으로 만드려면 나중에 많이 해봐야 겠지만, 현재는 시간이 부족하다.

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

조합 문제를 풀었다.

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

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

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

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

문제를 2가지 방법으로 풀었다.

첫 번째 방법은 노트를 없이 풀었는데, 문제를 잘 못 이해해서 시간초과가 났고,

두 번째 풀이는 메모이제이션을 이용해 코드를 작성했다.

1보다는 2를 먼저 채우는 방식으로 짰다.

Segment Tree

BOJ에 있는 블로그를 보고 공부했다.

일단 노트에 트리를 그리면서 어떤식으로 작동하는지 알게됐고, 아직 익숙하지 않다.

재귀함수 덩어리.