증명 블로그

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를 먼저 채우는 방식으로 짰다.


Segment Tree

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

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


재귀함수 덩어리.

음 보물찾기 문제.. BFS


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

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


음..

DP로 풀었다. 계단문제랑 비슷하다.


처음에는 그냥 3나눠지면 3하고 2되면 2하고 했는데, 그게 아니라 경우의수가 최소일 때 를 구하는것 이였다.

그래서 메모이제이션이랑 Stack을 이용해서 경로구하는거 까지 구현했다.


음.. 처음에 문제를 보고 난해했다.


그런데 조금 검색해보면서 확인해보니 위상정렬이나 DP로 풀 수 있다는걸 알고,

생각을 좀 해봤다.


일단 그래프인건 확실하고, 중등부여서 데이터도 적고 하니 DP로 풀자 생각했다.

DAG여서 1에서 끊어줘야되고, 시간초과가 나니까 Memorization도 해줘야 됐다.

그리고 순서를 표시하기 위해 disjoint-set도 했다. (트리구조로 parent를 찾아감)


+ Recent posts