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

[mins-n]

BOJ 17144 미세먼지 안녕

풀이

1. 미세먼지 확산
2. 공기청정기 작동
   • 배열을 초기화할 때 공기청정기 위치를 저장 안하여 오래 걸림

     구현

   • 미세먼지 확산: 현재 배열을 기준으로 다음 배열을 만들어야 하므로, cur_arr, next_arr 두 개의 배열을 사용
   • 공기청정기 작동: 위쪽은 반시계 방향, 아래쪽은 시계 방향으로 미세먼지를 이동시킴
   • 흡입은 거꾸로 진행

     BOJ 15686 치킨배달

     풀이

3. 치킨집 중 M개를 선택하는 조합을 구함
4. 각 집에서 선택된 치킨집까지의 거리를 구하고, 최소 거리를 구함
5. 최소 거리의 합을 구하고, 최소값을 갱신

   구현

6. 각 집에서 치킨집까지의 거리를 사전에 구해놓음
7. 백트래킹을 통해 치킨집 중 M개를 선택하는 조합을 구함
   • M개 미만의 경우를 계산할 필요가 없음
   • 출력이 최소값이므로, M개를 선택하는 경우만 고려
8. 각 집에서 선택된 치킨집까지의 거리를 구하고, 최소 거리를 구함
9. 최소 거리의 합을 구하고, 최소값을 갱신

   BOJ 14503 로봇청소기

   풀이

10. 현재 위치를 청소한다.
11. 현재 방향을 기준으로 반시계 방향으로 탐색하며 청소할 공간을 찾는다.
    • 청소할 공간이 없다면, 후진한다.
    • 후진할 수 없다면, 종료한다.
12. 청소할 공간이 있다면, 해당 방향으로 이동하고 1로 돌아간다.

    구현

    풀이와 같이 구현한다.

    BOJ 1182 부분수열의합

    풀이

    • 부분수열의 합이 S가 되는 경우의 수를 구함

      구현

13. 백트래킹을 통해 부분수열의 합이 S가 되는 경우의 수를 구함
14. 공집합을 제외하고 출력

    BOJ 17179 케이크 자르기

    풀이

    • 케이크를 N번 잘랐을 때, 가장 작은 조각의 길이가 최대가 되도록 자르는 문제
    • 이분 탐색을 생각 못했음

      구현

15. 각 cuts[i]에 대해 이진 탐색으로 최대 최소 길이를 찾음
    • 최소 길이로 cuts번 자를 수 있는지 확인하는 함수
    • 최소 길이를 찾는 함수(이분 탐색)

[Chaeniiiii]

고생하셨습니다 🙃