UP

문제 풀기 : 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번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이..

문제 풀기 : 10610번 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 문제 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수 만든다. 단, 수가 존재하지 않으면 -1을 출력한다. 문제풀이 최적의 해를 구하는 그리디 문제이다. 숫자들의 위치를 바꿔서 30의 배수가 되는 수 중 가장 큰 수를 찾으면 된다. 30의 배수가 되려면 첫째, 마지막 자리수가 0이어야 한다. 둘째, 3의 배수는 각 자리의 숫자 합이 3으로 나누어 떨어진다. 코드 TIP ''.join(배열) : 배열을 문자열로 바..

문제 풀기 : 2875번 2875번: 대회 or 인턴 첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N), www.acmicpc.net 문제 2명의 여학생과 1명의 남학생이 팀을 결성해서 나간다. N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다. 만들 수 있는 최대의 팀 수를 구한다. 문제풀이 최적의 해를 구하는 그리디 문제이다. 각각의 N명, M명에서 여학생이 2명, 남학생이 1명을 빼면서 팀을 결성한다. K명의 인턴쉽 참가자가 필요하기 때문에 팀을 결성하고 남은 N + M명이 K보다는 클 때 만든다는 조건을 ..

문제 풀기 : 11047번 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 준규가 가지고 있는 동전은 총 N종류이다(각각의 동전을 매우 많이 가지고 있다.) 동전을 적절히 사용해서 동전의 합을 K로 만들려고 한다. 이 때 필요한 동전 개수의 최솟값을 구한다. 문제풀이 최적의 해를 구하는 그리디 문제이다. 동전의 합을 크게 만들기 위해선 동전의 종류 중 가치가 큰 동전의 필요한 개수부터 빼나가면 된다. 전체코드 # n : 동전의 종류 수, k ..