TIL 15일차
2021. 1. 5. 19:53
오늘도 어김없이 solved.ac 클래스 올리기
github + sns 프로젝트인 Tentagram 시작했다. api 설계를 했다.
-----
오늘 해결한 클래스 5 백준 문제들
1516 게임개발 - 위상정렬 + dp - ACM Craft와 같았다.
1562 계단 수 - dp - dp인것을 알아차리기 어려웠다.
*1644 소수의 연속 합 - 에라토스테네스의 체 + 슬라이딩 윈도우
1647 도시 분할 계획 - 크루스칼 - 최소 스패닝 트리를 만들고 마지막 edge의 cost(선택한 간선중 가장 cost 가 큰 간선)를 총 cost에서 빼줌으로 해결
*1799 비숍 - 백트래킹 - queen처럼 했다가 시간초과가 났다. 찾아보니 체스의 화이트 판과 검은색 판을 나누어서 백트래킹을 진행한뒤 최대값을 구하는 방식으로 보다 빠르게 진행할 수 있었다. n은 10