https://school.programmers.co.kr/learn/courses/30/lessons/161989
위 문제처럼 그냥 항상 똑같은 길이를 쓸수 있다고 가정해서 최소 몇개를 써야 전체 길이를 커버하냐는 문제는 그리디스러운게 이해가 가는데,
여기서 문제를 조금만 변형해서 똑같은 길이가 아닌 다른 길이들이 input으로 주어지는 경우에서 최소 몇개를 써야 전체가 커버가 되냐는 문제
역시 그리디로 생각하고 풀 수 있나요? 만약 그렇다면 기준을 어떻게 잡아야하고, DP로 풀어야한다면 점화식을 어떻게 구하나요?
아니면 완탐으로 풀어야하나요?
다른 길이들이 주어져도 그냥 가장 긴 거 쓰면 되잖아
반례있을거같은데...
문제대로라면 이미 칠해진 칸에 또 칠해도 되고 같은 칸에 여러 번 칠해도 되는데 그럼 무조건 긴 게 이득이지 더 짧은 거 이용한 해에서 길이를 더 늘린다고 해서 이득이면 이득이지 손해볼게 없는데
같은 경우는 왼쪽에서 오른쪽으로 인덱스 돌면서 골라주면 되는데 다른 길이들이 주어지면 가잘 긴걸 어느 지점에 쓸지 결정해줘야 할거 같은데 이때 적용되는 알고리즘이 뭔가요?
그리고 변형된 문제에서는 겹치면 안된다는 조건까지 추가하겠습니다!
더긴걸어디에쓰느냐하는걸 결정하는게 좀그럼 댓글만보면 암튼 긴걸 앞에다 쓴다하는걸로 읽었음
사실 저 문제를 그리디가 아니게 하는 방법은 그냥 횟수 제한을 풀면 됨
길이가 여러가지고 겹치면 안되는 경우는
https://en.m.wikipedia.org/wiki/Change-making_problem
이 문제와 같고, 냅색dp가 최선인듯 - dc App
뭔가 동전같이 정해진 딱 맞춰야하는 갯수가 있는 것은 아니고, 특정 지점만 커버한다면, 겹치지 않는 선에서 나머지 지점은 써도되고 안써도 되는데 이래도 DP로 접근해야하나요??
아 주어진 자리 밖도 칠해도 되는거면 가장 긴걸로 칠하는게 당연히 이득이라 그리디하면 될듯 - dc App