https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제풀이 위 문제는 거스름돈 5원과 2원으로 주어진 돈을 거슬러 줘야 하는데 이때 동전을 최소한으로 사용하여 거슬러 줘야 한다. 먼저, 15원까지 동전의 수를 나열해 보았다. 나열해 본 결과 반복되는 패턴이 있음을 알 수 있다. 주어진 돈이 5의 배수가 아니면 주어진 돈 n 원에 대한 동전의 개수는 n - 2원에 대한 동전의 개수 + 1인 것을 알 수 있었다. 때문에 위 문제는 다이내믹 프로그래밍을 활용하여 문제를 해결할 수 있다. var n = Int(readLine()!)! var result = 0 var dp..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이과정 해당 문제는 Dictionary을 활용하면 문제를 해결할 수 있다. let _ = Int(readLine()!)! var nList: [Int] = readLine()!.split(separator: " ").map { Int($0)! } let _ = Int(readLine()!)! var mList: [Int] = readLine()!.split(se..

https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 풀이과정 이번 문제는, N x N 보드에 무작위로 4가지 색의 사탕이 올라가있다. 보드에 올라가있는 사탕 중 인접한 색이 다른 사탕 2개의 자리를 바꿔 가로 혹은 세로로 연속한 같은 색의 사탕의 최댓값을 출력하는 문제이다. 문제를 처음 읽고 풀이를 생각했을 때 색이 서로 다른 인접한 사탕 2개를 탐색하여 위치를 변경하고 동일한 색의 연속한 사탕의 수를 계산하였다. // 첫 제출 let N = Int(readLine()!)! var input: [[String]] = [] var map: [[String]] = []..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이과정 이번 문제는 주어진 백준이 주어진 N + 1일 동안 업무를 했을 때 벌 수 있는 최대 누적 금액을 구하는 문제이다. 최대 누적 금액을 구하는 문제이기 때문에 DP를 활용하면 쉽게 접근할 수 있겠다는 생각이 들었다. 처음엔, DP 배열에 일차 별로 벌 수 있는 최대 누적 금액을 담으려 했지만, 그러면 일을 시작하고 끝나는 날을 카운팅 하기 쉽지 않았다. 때문에 끝나는 날을 기준으로 DP에 누적 금액을 담았다. 예를 들어, 1일차 상담을 시작하면 상담이 끝나는 날은 4일이다. 때문에 DP[4]에 해당 금액을 담는다. 이런 식으로..

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이과정 해당 문제는 주어진 행렬을 통해 좌표의 경로를 찾는 문제이다. 먼저, 예제를 풀이하자면 위 예제를 통해 (0, 3), (1, 6), (3, 4), (3, 5), (4, 0), (5, 6), (6, 2)의 좌표가 1인 것을 알 수 있다. 이를 보기좋게 정점으로 나눠 표현하면, 0 0 -> 3 -> 4 -> 0 / 0 -> 3 -> 5 -> 6 -> 2 1 1 -> 6 -> 2 2 X 3 3 -> 4 -> 0 / 3 -> 4 -> 6..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이과정 문제를 정리하면, 계단마다 점수가 있다. 계단은 1칸 혹은 2칸씩 오를 수 있다. 하지만, 연속된 세 개의 계단을 모두 밟을 수는 없다. 이때 얻을 수 있는 점수의 최댓값을 구해야 한다. 중요한 키워드만 정리해 보았다. 해당 문제는 DP를 활용하여 풀 수 있다. 각 계단을 올랐을 때 포인트의 최댓값을 알고 있으면 해당 포인트에 앞으로 오를 계단의 포인트를 더해주면 해결할 수 있다. 계단 수가 1번부터..