🔗문제 보러가기 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 🧑‍💻풀이 과정 동적 계획법(Dynamic Programming)과 위상 정렬(Topological Sort)를 사용해 풀 수 있습니다. 진입 차수가 0인 노드(v)에서 다른 인접 노드(other)로 향할 때, 다음 로직만 추가해주면 됩니다. *constructionTimes[i] : i 번째 건물의 건설 시간 *answers[i] : 먼저 지어야 하는 건물을 짓고 난 후, i 번째 건물까지 짓는 데 걸리는 최소 시간 answers[o..

🔗문제 보러가기 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 🧑🏻‍💻풀이 과정 N자리 숫자에서 일의 자리가 0 ~ 9로 끝나는 계단 수들의 개수를 알아봅시다. 먼저, \( N = 1\)일 때는 다음과 같습니다. [ N = 1 일 때 ] i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8 i = 9 0 1 1 1 1 1 1 1 1 1 [ N = 2 일 때 ] i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8 i = 9 1 1 2 2 2 2 2 2 2 1 [ N = 3 일 때 ] i = 0 i = 1 i = 2 i = 3 i = 4 i..

🔗문제 보러가기 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 🧑🏻‍💻풀이 과정 Dynamic Programming 문제입니다. \( n = 1\), \( n = 2\), ... 일 때의 경우의 수를 한 번 점검해보면, 패턴이 보이는 것을 알 수 있습니다. /* - 어떤 한 행에 있어서 가질 수 있는 경우의 수는 다음과 같은 3가지 [][], [o][], [][o] */ [][][o][][][o] n = 1 : 1 1 1 n = 2 : 3 2 2 n = 3 : 7 5 5 n = 4 : 17 12 12 ... [ ][ ]의 경우의 수는 n - 1번째의 [ ][ ] + [o][ ] + [ ][o] 값입니다. [o][ ]과 [ ][o]의 경우의 ..

🔗문제 보러가기 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 🧑🏻‍💻풀이 과정 DP(Dynamic Programming)로 풀 수 있습니다. 알고리즘은 다음과 같습니다. 1. (0, 0)부터 시작하여 0행과 0열에 대해 누적합을 저장해 나가며, 초기화를 해줍니다. 예제 입력 1번을 예로 들면 다음과 같이 합니다. // 원본 입력 데이터 1 2 3 4 0 0 0 5 9 8 7 6 // 누적합 적용 후 1 3(2+1) 6(3+3) 10(6+4) 1 (0+1) 0 0 5 10(9+1) 8 7 6 2..

🔗문제 보러가기 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 🧑🏻‍💻풀이 과정 피보나치 함수를 호출했을 때, \( n = 0 \) 또는 \( n = 1 \)일 때의 0과 1의 출력 개수를 세야 합니다. (즉, 위 문제에서 주어진 소스 코드에서 if(n == 0)과 if (n==1)에 해당할 경우) 1. Top-down 방식으로 DP 배열을 통해 중복 계산 최소화 방법 시도 (실패) 피보나치 함수를 재귀로 구현했을 때의 문제점이 바로 중복 계산입니다. 중복 계산이 이루어지기에 시간이 터무니없이 많이 걸리는 것이고, 이것을 개선하기 위해 DP 배열을 사용하여 이미 계산된 N이라면 계산하지 않는 것이죠. 하..

🔗문제 보러가기 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 🧑🏻‍💻풀이 과정 \( n = 1\)부터 하나씩 그려보면, 피보나치 수열의 규칙이 생깁니다. \( n = 1\)과 \( n = 2\)를 베이스로 삼아, \( n = 3\)부터는 \( n - 2\)와 \( n - 1\)을 가지고 조합해 나가는 방식이다 보니, 피보나치 수열과 같은 규칙이 생기는 것 같네요. ✏️ 소스 코드 및 결과 #include #include using namespace std; void SetFastIO() { ios::sync_with_stdio(..