GitHubSeob

문제 https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제풀이 이 문제는 수학적으로도 풀 수 있지만 DP로도 풀 수 있어서 DP로 풀었다. 1부터 N까지 거스름돈 동전 개수를 나타내기 위한 won 벡터와, 2원, 5원 동전이 들어있는 coin벡터를 선언했다. 거슬러 줄 수 없으면 -1을 출력해야 되기 때문에 벡터를 -1로 초기화했다. DP를 사용할 것이기 때문에 0원의 동전의 개수는 0으로 설정해 준다. 2원 동전부터 시작하여 2의 배수가 되면 2원을 뺀 금액의 동전의 개수+1을 한다. 5원 동전도 마찬가지로 5원부터 5원을 뺀 금액의 동전의 개수+1을 한다. 9..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12907 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제풀이 이전에 풀었던 백준 문제와 똑같다. 동적 계획법인 dp를 이용해 풀었다. 동전의 구성은 같지만, 순서만 바꿔서 다른 경우는 같은 경우로 친다. DP[n] = DP[n-원]이 기본 형태이다. 1원은 1원 동전으로 만들 수 있다. 2원은 1원의 경우의 수와 같다. 3원은 1원의 경우의 수와 같다. . 2원은 기존 방법에서 추가로 더한다. 2원은 2원의 동전으로 만들 수 있다. 1+1 3..