신년맞이 boj - day5

4796 캠핑

단순한 생각-

예를 들어 8일 중에 5일을 사용할 수 있으며 총 휴가가 20일이면

8일(5일)-8일(5일)-4일=14일을 캠핑할 수 있다

계산 방법 그대로 휴가를 일 수로 나누고 나머지를 더하면 된다

 

근데 여기서 함정은, 남은 일수가 연속 일수보다 큰 경우다

위에서는 8일 중에 5일을 사용할 수 있는데 남은 일수가 4일이라서 그냥 넣으면 됐다

근데 만약 남은 일수가 6일이라면? 최대 5일밖에 사용할 수 없다

이 두 가지 경우를 주의해 주면 되었다

 

github.com/proqk/Algorithm/blob/master/greedy/4796%20%EC%BA%A0%ED%95%91.cpp

 

2891 카약과 강풍

각 팀이 가지고 있는 카약의 수를 인덱스로 만들어서 더하거나 빼면 되었다

처음엔 모든 팀이 카약을 1개씩 가지고 있다고 하고, 입력을 받으면서 없는 팀과 더 있는 팀을 +1 -1한다

그리고 반복문을 돌면서 카약이 없는 팀이면 양쪽 팀을 보면서 숫자를 조절하면 되는데,

맨 끝 팀은 그 바로 옆 팀한테밖에 못 빌린다는 점을 주의한다

 

github.com/proqk/Algorithm/blob/master/greedy/2891%20%EC%B9%B4%EC%95%BD%EA%B3%BC%20%EA%B0%95%ED%92%8D.cpp

 

 

13164 행복 유치원

쉬워보였는데 은근 어려웠다

쉽게 생각했을 때는 어차피 오름차순 순서대로 k개씩 묶으면 되는 거 아닌가 해서,

전체 학생을 돌면서 k번 반복문으로 각각의 그룹 묶으면서 res를 구하고, 마지막 남은 사람이 있다면 혼자 팀인 0으로 하려고 했다

근데 꼭 오름차순으로 그룹을 묶었을 때 최소가 된다고 할 수 없는 것 같기도 했다(아마)

 

그래서 모든 인접에 대한 차를 담은 배열을 만들고 내림차순 정렬했다

그리고 차이가 가장 큰 k-1개를 버린 나머지 k~나머지를 더한다

 

github.com/proqk/Algorithm/blob/master/greedy/13164%20%ED%96%89%EB%B3%B5%20%EC%9C%A0%EC%B9%98%EC%9B%90.cpp

 

 

13305 주유소

제일 싼 곳에서 최대한 많이 주유하는 게 무조건 이득이다

 

첫시도-

현재 위치의 기름값보다 더 싼 기름값이 나올 때까지 index++, 이후 index만큼 기름값을 계산

하지만 index만큼 기름값을 계산 부분에서 뭔가 제대로 되지 않았는지 자꾸 틀린 답이 나왔다

 

다음 시도-

더 싼 기름값이 나올 때까지 가는 건 같지만, 바로바로 가격 계산해서 더한다

더 싼 기름이 나오면 기름값을 갱신한다

맨 처음은 무조건 산다

 

분명 맞는 것 같은데 틀렸습니다가 뜬 이유는 안에 들어가는 수 범위가 엄청 커서 long long을 써야 했다

 

github.com/proqk/Algorithm/blob/master/greedy/13305%20%EC%A3%BC%EC%9C%A0%EC%86%8C.cpp