[김민선] 1주차 문제풀이

[mins-n]

BOJ 14501 퇴사

풀이

• 모든 경우의 수를 탐색하면서 최대 수익을 구함

  구현

• dp 배열을 선언하고 dp[i]는 i일 째 얻을 수 있는 최대 수익을 저장
  1. 상담을 하지 않는 경우: dp[i + 1]는 dp[i]와 dp[i + 1] 중 큰 값으로 갱신
  2. 상담을 하는 경우: dp[t + i] = 상담 수익 + dp[i]와 dp[t + i] 중 큰 값으로 갱신

     BOJ 1021 회전하는 큐

     풀이

• 목표 idx까지 이동하는 최소 횟수를 구함
• 왼쪽으로 이동하는 경우와 오른쪽으로 이동하는 경우를 나누어 생각하고
• greedy 방식으로 풀이

  구현

  1. deque에 1부터 n까지의 수를 넣는다.
  2. 목표 idx를 찾아 왼쪽으로 이동하는 경우와 오른쪽으로 이동하는 경우를 나누어 생각한다.
  3. 둘 중 최소 횟수를 구한다.
  4. 해당 방향으로 이동하며 정답을 구한다.

     BOJ 3896 소수 사이 수열

     풀이

• 에라토스테네스의 체를 사용하여 소수를 구한 후 주어진 수에 대해 가장 가까운 소수를 찾는다.
  • 처음에 에라토스테네스를 사용 안하여 시간 초과 발생

    구현

    1. 에라토스테네스의 체를 사용하여 소수를 구한다.
    2. 주어진 수가 소수인지 확인
    3. 주어진 수가 소수인 경우 0 출력
    4. 주어진 수가 소수가 아닌 경우 입력된 수보다 작은 소수, 큰 소수를 찾아 차이를 출력

       BOJ 2636 치즈

       풀이

• 가장자리 치즈를 찾아 녹이기
• 가장자리 치즈를 찾기 위해 BFS를 사용
• https://ongveloper.tistory.com/159
  • 고민후 못 품
  • 위 블로그 코드 안보고 풀이만 참고함

    구현

• 큐를 2개 사용하여 구현
  • 가장자리를 넣을 큐
  • BFS 탐색을 위한 큐
    1. 0, 0에는 항상 공기가 있으므로 (0, 0)부터 BFS로 탐색 a. 치즈인 경우 가장자리 큐에 넣기 b. 공기인 경우 BFS 탐색을 위한 큐에 넣기
    2. 가장자리 치즈를 녹이기
    3. 치즈가 다 녹았는지 확인
    4. 치즈가 다 녹았으면 시간 및 1시간 전에 남은 치즈 개수 출력

       BOJ 2617 구슬 찾기

       풀이

• 각 구슬에 대해 상위 구슬, 하위 구슬 탐색
• 상위 구슬 혹은 하위 구슬의 개수가 n/2 이상이면 무게가 절대로 중간이 될 수 없음

  구현

  1. map을 사용하여 상위 구슬, 하위 구슬을 저장
     • map을 사용 안하고 graph로 구현하면 더 좋을 것 같음
  2. queue를 사용하여 BFS로 상위 구슬, 하위 구슬 탐색
  3. 상위 구슬 혹은 하위 구슬의 개수가 n/2 이상이면 무게가 절대로 중간이 될 수 없음

[proysm]

고생하셨습니다 !! ⍢