2024-01-06

<2024-01-06>

• DP 문제 해결
  ✔️ Gold 4 2133 타일 채우기
  ㄴ 벽을 가로 2k마다 끊어서 생각해야 함. O(N^2)
  ✔️ Gold 5 17070 파이프 옮기기 1
  ㄴ dp 2차원으로 두고 그냥 규칙대로 밀면 됨
  ✔️ Silver 4 9656 돌 게임 2
  ㄴ 약간 생각이 필요한 문제. dp[N]은 돌 N개 상태에서 선공의 승리 여부로 둔다. dp[i] = max(!dp[i-1], !dp[i-3]);
  
• 실버 랜덤 디펜스
  ✔️ Silver 5 11637 인기 투표
  ㄴ 지문 그대로 구현하면 맞는 문제.
  ✔️ Silver 4 12755 수면 장애
  ㄴ 최적화 1도 없이 그냥 돌리면 맞는 문제. 놀랍다!
  ✔️ Silver 3 14223 작은 정사각형 1
  ㄴ "경계 위에 있는 점은 안에 있는 것이 아니다" 라는 조건을 주의하자.
  
• 골드 랜덤 디펜스
  ✔️ Gold 1 6757 팰린드롬 진법
  ㄴ O(N)으로 처리할 수 없으므로 적당히 커팅하는 방법을 생각해야함.
  ㄴ 만약 2자리 팰린드롬을 미리 처리한다면, 3자리부터는 $O(\sqrt N)$으로 끊을 수 있음.
  ㄴ 2자리는 b진법일 때 X = $p*b+p$ 형식임 (p<b). X%p==0일 때 b=(X/p)-1.
  ㄴ $p*p+p$ < X로 p의 범위를 잡고 for문 돌리면 $O(\sqrt N)$으로 처리됨.
  ✔️ Gold 4 2916 자와 각도기
  ㄴ 입력받은 N개의 각도에 대해서 gcd(360, a)의 배수를 dp 배열에 활성화하고, 이후 dp 배열을 순회하면서 가능 여부를 찾는다.
  ㄴ 정수 각도는 360개이므로 $O(360^2 * K)$에 해결 가능하다.
  ✔️ Gold 1 18436 수열과 쿼리 37
  ㄴ 세그먼트 트리를 알면 바로 풀 수 있다.
  ㄴ 나는 Node 구조체를 만들어서 odd, even 개수를 저장하도록 했는데, 그러지 않아도 충분히 풀린다.