그리디 알고리즘 (2) 썸네일형 리스트형 백준 1783번 - 병든 나이트(C++/Greedy/그리디 알고리즘/ 경우의수 분석) https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다. 2칸 위로, 1칸 오른쪽 1칸 위로, 2칸 오른쪽 1칸 아래로, 2칸 오른쪽 2칸 아래로, 1칸 오른쪽 병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보.. 백준 10610번 - 30 (C++/greedy(그리디)알고리즘) 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 접근법 이 문제는 문제 예시를 보고 풀이법을 유추해낸 특이한 경우이다. 가장 큰 힌트를 얻었던 것은 30으로 나누어 떨어지는 숫자들은 모두 해당 숫자를 내림차순으로 내린것과 같다는 것이 보였다. 그럼 만약 30으로 나누어 떨어지면 내림차순으로 정렬해주면 되겠다 생각을 했고, 30으로 나누어 떨어지는 조건만 찾으면 됐다. 1. 모든자리의 수의 합이 3이 되어야 한다. (3의 배수 조건) 2. 끝자리는 0으로 끝나야 한다. (10의 배수.. 이전 1 다음
