[백준 - 1014] 컨닝
문제: https://www.acmicpc.net/problem/1014
앉을 수 없는 자리를 1, 앉을 수 있는 자리를 0으로 표현해 동적계획법으로 풀었다.
구현도 번거로웠지만 사실 가장 힘들었던건 비트연산자의 우선순위를 깜빡 했다는 점이다.
for(int chk=3;chk<sz;chk=chk<<1)
{
if(chk&j==chk)
...
}인접하게 배치할 수 없도록 만든 이 코드가 뚫려서 자꾸 예제가 안나왔었다.
디버깅 하느라 시간을 꽤나 날렸지만 이럴 때 날려야 중요한 테스트 때 실수를 안할 수 있으니 다행이라고 생각한다.
[백준 - 2934] LRH 식물
문제: https://www.acmicpc.net/problem/2934
L,R을 입력받을 때 마다
L과R 위치의 값을 더해서 출력해주고 그 값을 0으로한다.
그 후 (L,R) 범위에 1씩 더해준다.
범위에 값을 더해야 하므로 느리게 갱신되는 세그먼트 트리를 사용하면 된다.
[백준 - 2188] 축사 배정
문제: https://www.acmicpc.net/problem/2188
늘 미뤄왔던 네트워크 플로우와 이분 매칭을 공부하고 풀어보았다.
플로우 문제는 이게 플로우로 풀 수 있는지 알아채는게 제일 어렵다고 하더라.
더 많이 풀어봐야 할 것 같다.
[백준 - 1006] 습격자 초라기
문제: https://www.acmicpc.net/problem/1006
원형 모양이라 시작지점과 끝지점이 연결 되어 있는부분을 처리하는데 유의해야 한다.
시작 지점에서 끝 지점으로 뻗은 케이스에 따라 4가지로 분류가 가능하다.
끝 시작
o o
o o
o o
......
......
o o
.....
.....
이 4가지로 따로 DP를 돌려 끝부분에 주의하며 답을 구하면 된다.
[백준 - 1824] 도미노
문제: https://www.acmicpc.net/problem/1824
격자모양에 2x1 칸으로 놓는 문제는 이분매칭을 바로 생각해 봐야 하는 것 같다.
체스판 무늬로 생각하여 검은칸과 흰칸으로 나눠 이분매칭을 하였다.
처음에는 필요한 edge만 생성하려다가 구현 방법이 생각이 안나서 포기하고 저번처럼 배열을 만들어서 edge를 표현했다.
그래서 맞은 사람중에 가장 느린 알고리즘이라는 결과가 나온 것 같다.
정말 압도적으로 느리다...
필요한 edge만 생성하는 방식을 꼭 익혀야겠다.
