그리디 알고리즘 문제 거스름 돈 [문제] 당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한이 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다. [입력] 1260 [출력] 6 정답 n = int(input()) coins = [500, 100, 50, 10] cnt = 0 for coin in coins: cnt += n // coin n %= coin print(cnt) 큰 수의 법칙 동빈이의 큰수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰수를 만드는 방법이다. 단, 배..

[백준 C++] 알고리즘 10250. ACM 호텔 작성 코드 #include using namespace std; int main() { int H, W, N, o; scanf("%d", &o); for (int i = 0; i < o; i++) { int p = 1; int x, y = 1; scanf("%d %d %d", &H, &W, &N); while(p

[백준 C++] 알고리즘 2869. 달팽이는 올라가고 싶다. 작성 코드 #include using namespace std; int main() { int A, B, V; scanf("%d %d %d", &A, &B, &V); int sum = 1; int diff = (V - A) / (A - B); if ((V - A) % (A - B) == 0) sum += diff; else sum += diff + 1; printf("%d", sum); } 후기 A, B, V간의 규칙을 찾아내면 가볍게 풀어낼 수 있는 문제였습니다. 달팽이가 도착하기 까지 걸리는 일 수를 구하는 문제인데 문제 안에 숨어있는 규칙을 찾아내면 (A - V) / (A - B) 일이 나옵니다. 이 때 계산 값의 나머지가 0이면 sum에..

[백준] 알고리즘 1065. 한수 문제 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다. 출력 첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다. 예제 입력 110 예제 출력 99 예제 입력 1 예제 출력 1 예제 입력 210 예제 출력 105 예제 입력 1000 예제 출력 144 #include #include using namespace std; int dgtSequence(int n) { if (n == 1000)..

[백준] 알고리즘 4673. 셀프 넘버 문제 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다. 33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, ..

백준 알고리즘 1948. 임계경로 문제 월드 나라는 모든 도로가 일방통행인 도로이고, 싸이클이 없다. 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다. 이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 만나기로 하였다. 그렇다고 하였을 때 이들이 만나는 시간은 출발 도시로부터 출발한 후 최소 몇 시간 후에 만날 수 있는가? 즉, 마지막에 도착하는 사람까지 도착을 하는 시간을 의미한다. 어떤 사람은 이 시간에 만나기 위하여 1분도 쉬지 않고 달려야 한다. 이런 사람들이 지나는 도로의 수를 카운트 하여라. 출발 도시는 들어오는 도로가 0개이고, 도착 도시..