5주차
개미와 진딧물
- 격자가 주어짐
- 진딧물에서 M칸 이내에 있는 개미만 살아남을 수 있음
- 최종 살아남는 개미의 개수 구하기
- 진딧물 기준 M step BFS 를 수행하고, 만나는 개미를 체크함
- 전체 개미 개수 - 최종 남은 개수 = 정답
모래섬
- 격자가 주어짐
- 물과 모래가 주어짐
- 물은 1일단 상/하/좌/우로 한칸씩
- 최초로 모래섬이 2개 이상 되는 날짜 구하기
- 처음에는 물이 점령하는 시간 + 이분탐색인줄 알았음
- 섬의 상태가 단조 증가/단조 감소 같은 것이 아니라 이분탐색 불가
- 완전탐색 + BFS : 시간순으로 일일이 확장 + 몇개의 그룹인지 체크
수 이어 붙이기
- 두 자리 숫자 8개 주어짐(10 ~ 99)
- 이어붙이는데 끝과 시작이 같으면 서로 병합 가능 : ex) 18 + 89 = 1889 or 189
- 이어붙였을때 가장 작은 숫자 구하기
- 완전탐색으로 접근
구슬게임
- 두 명이 구슬을 갖고 시작(100개)
- 이기면 1개 갖고 오고 지면 1개 뺏기고, 비기면 아무것도 아님
- K 번 수행했을때 한쪽이 0이 되는 경우의 수
- dp[몇번][A가 갖고 있는 개수][B가 갖고 있는 개수]
- 생각해보면 A + B = 전체 구슬의 개수 = 고정이므로
- dp[몇번][A가 갖고 있는 개수]로만 해도 됨
- 매 횟수마다 dp[x][0], dp[x][n+m]의 횟수를 정답에 더해주고
- dp[x][p]
- 지거나 dp[x + 1][p - 1]
- 이기거나 dp[x + 1][p + 1]
- 비기거나 dp[x + 1][p]
- 시간복잡도로도 안전함
newbieski