반응형
반응형
알고리즘 그리디 힌트 손님이 펜션에서 가장 오랫동안 머물 수 있는 방을 찾아준다. 풀이 아이디어는 간단하다. 손님이 오늘부터 가장 오랫동안 머물 수 있는 방을 찾아주면 된다. 여기서 잔재주를 부려보면 펜션의 상태를 char형으로 그대로 저장 말고 0,1로 바꾸어 저장해준다. (O : 1, X : 0) 이러면 비교 연산자를 사용하지 않고 조건문 처리가 가능하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 #include using namespace std; int in..
알고리즘 그리디 힌트 가장 칼로리가 높은 토핑만 생각한다. 풀이 도우는 무조건 포함해야 하므로 cost(가격)와 cal(칼로리)를 도우의 가격과 칼로리로 초기화해준다. 토핑의 가격들이 입력되면 내림차순으로 정렬해준다. (토핑은 한 번만 사용할 수 있으므로 남아 있는 토핑 중 가장 칼로리가 높은 토핑만 고려하면 된다.) 현재의 칼로리/달러가 i번째 토핑을 추가했을 때의 칼로리/달러보다 클 경우 cal과 cost를 갱신해준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include #include using namespace std; int cmp(int a, int b)..
알고리즘 그리디 힌트 가장 비싼 화폐부터 거슬러 준다. 풀이 이 문제는 대표적인 그리디 문제다. 거슬러 줄 수 있는 가장 비싼 화폐부터 거슬러 주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include using namespace std; int main(){ int money[8]={10,50,100,500,1000,5000,10000,50000}; int n,cnt=0; cin>>n; for(int i=7;i>=0;i--){ cnt+=n/money[i]; n%=money[i]; } cout
알고리즘 그리디, 백트래킹 힌트 매 시행마다 목표 채널과 현재 채널중 큰 것을 골라 빼거나 작은 것을 골라 더한다. 풀이 a와 b의 대소 관계가 고정되어 있지 않기 때문에 임의로 a>b로 잡아 주었다. 변경할 수 있는 수가 1, -1, 5, -5, 10, -10 인 것에 주목하자. (절대값이 같은 두 수가 3쌍이다.) a에 10을 뺀 것은 b에 10을 더한 것으로 치환할 수 있다. ( 현재 온도를 x도 높인 것은 목표 온도를 x도 낮춘것 과 같고, 현재 온도를 x도 낮춘 것은 목표 온도를 x도 높인 것 과 같다. ) 따라서 두 수 중 큰 수만 값을 줄여주면 되기 때문에 임의로 a와 b의 대소관계를 정해주는 것은 일반성을 잃지 않는다. 시행 횟수에 영향을 미치지 않는다. d 배열에 양수 값만 필요하고 a,..