[유수민] 2주차 문제풀이

[proysm]

17179 케이크 자르기

핵심 풀이

• 이분탐색에서 mid값을 가장 작은 조각의 길이의 최댓값으로 정의한다.
• 자른 횟수 잘라야하는 횟수를 비교해가며 mid값을 갱신하면, 가장 큰 mid 값을 찾을 수 있다.

  // 현재 자른 횟수(cuts)와 잘라야하는 횟수(cut[i]) 비교
  // 마지막으로 자른 위치(cuttedPosition)
  if(cuts == cut[i] && l-cuttedPosition < mid) {
  en = mid - 1;
  }
  else if(cuts < cut[i]){
  en = mid - 1; 
  }
  else{
  st = mid + 1;
  } 

• 테스트케이스는 통과했지만 계속 틀렸던 이유는 l-cuttedPosition < mid를 확인하지 않아서다.
• 마지막 케이크 조각(l-cuttedPosition) 를 확인해야 한다.

알고리즘

• 이분탐색
• 브루트포스 : N과 M의 범위가 충분히 작다면 순열을 사용하여 풀이할 수 있다. (이 문제에서는 불가능)

1182 부분수열의 합

핵심 풀이

• dfs를 이용하여 해당 인덱스의 값을 수열에 더하거나, 더하지 않는 경우를 모두 확인한다.
• 처음에 문제를 착각했던 부분이 수열이 연속된 인덱스여야 한다고 생각했는데, 아니였다.

알고리즘

• dfs

14503 로봇 청소기

핵심 풀이

• 로봇 청소기가 동, 서, 남, 북으로 이동하는 것을 헷갈리지 않는 것이 중요하다.
• d=0 북, d=1 동, d=2 서, d=3 남

  int dx[4] = {-1, 0, 1, 0};
  int dy[4] = {0, 1, 0, -1};

  알고리즘

• bfs

15686 치킨 배달

핵심 풀이

• 도시의 치킨 거리가 가장 작은 경우는, 치킨집을 M개 남기는 것이다.
• 따라서 폐업시킬 치킨집(|전체치킨집개수| - M)을 순열(next_permutation)을 이용하여 고르고, 치킨 거리를 구한다.

  
  do{

}while(next_permutation(brute.begin(), brute.end()));

#### 알고리즘
- 브루트포스

# 17144 미세먼지 안녕!
#### 핵심 풀이
- 반시계, 시계 방향으로 한 칸씩 옮기는 알고리즘 / 확산하는 알고리즘 -> 3가지를 구현한다.
- 공기청정기가 있는 위치를 조심해서 구해야 한다.

#### 알고리즘
- 시뮬레이션

[Chaeniiiii]

고생하셨습니다 :)

[mins-n]

고생하셨습니다!!

[jundm]

고생하셨습니다!