알고리즘을 좋아하는 나

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를 참고함.

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

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

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

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

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

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

조합 문제를 풀었다.

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

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

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

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

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

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

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

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

음 보물찾기 문제.. BFS

BFS를 사용하며 visited를 잘못써서 시간초과가 났었고, for문을 break하는걸 넣어놓고 안빼서 계속 틀렸었다.

2005년도 초등생은 BFS를 할줄 안다니.. 대단하네