[정현우] 1주차 문제풀이

[cookingTorch]

BOJ 14501 퇴사

• 64 ms
• DP

  풀이

  1일 ~ N일 상담, N + 1일 퇴사 -> 0일 ~ N - 1일 상담, N일 퇴사 dp[i] = i일 전까지 최대 금액 합 i일의 상담을 진행하는 경우 dp[i + T] 갱신 i일의 상담을 진행하지 않는 경우 dp[i + 1] 갱신 퇴사 전까지 최대 금액 합 dp[N]

BOJ 1021 회전하는 큐

• 64 ms
• 큐

  풀이

  큐에 1 ~ N 숫자 삽입 회전 = 큐 앞에서 숫자를 뽑고 뒤에 삽입 원하는 숫자가 나올 때까지 회전 회전 수와 역방향 회전했을 때의 회전 수를 비교 역방향 회전 수 = (큐 사이즈) - (회전 수) 더 작은 회전 수 누적

BOJ 3896 소수 사이 수열

• 84 ms
• 에라토스테네스의 체 + 이분 탐색

  풀이

  primes 배열에 100,000개의 소수 저장 k가 소수일 경우 0 출력 k가 소수가 아닐 경우 primes에서 k를 넘는 최소 소수 위치 이분 탐색 소수 사이 수열 길이 = (해당 소수) - (한 칸 이전 소수)

BOJ 2636 치즈

• 64 ms
• BFS

  풀이

  map 1 차원 변환 q: 지금 녹는 치즈들 q2: BFS 큐 (1, 1)에서 첫 번째 BFS 시작 q2에 위치 삽입하면서 BFS 치즈를 만나면 다음에 녹는 치즈이므로 q에 삽입 q에 저장된 치즈들 각각에서 다음 BFS 실행

BOJ 2617 구슬 찾기

• 112 ms
• 플로이드-워셜

  풀이

  u보다 가벼운 v들 lighter[u][v]에 표시 u보다 무거운 v들 heavier[u][v]에 표시 u > k이고 k > v이면 u > v u < k이고 k < v이면 u < v lighter 또는 heavier에 표시된 개수가 N / 2를 초과하면 중간이 될 수 없는 구슬

[mins-n]

고생하셨습니다!!!

[Chaeniiiii]

고생하셨습니다 🙂