알고리즘/백준93 [백준/C,C++] 2579번: 계단 오르기 www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 점화식을 생각하는 데 오래 걸렸던 문제입니다. 핵심은 현재 계단을 밟을 때 몇 칸을 올라왔는지 기억하며 풀어야 한다는 것입니다. 1번 계단(10) 2번 계단(20) 3번 계단(15) 4번 계단(25) 5번 계단(10) 6번 계단(20) 1칸 올라 도달 10 30 35 50 65 65 2칸 올라 도달 20 25 55 45 75 예를 들어 4번 계단을 봅시다. 4번 계단을 밟을 수 있는 경로는 3번 계단에서 1칸 올라 밟거나 .. 2021. 3. 7. [백준/C,C++] 1932번: 정수 삼각형 www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 크게 어렵지 않은 DP 문제입니다. 삼각형에서 가장 왼쪽 혹은 오른쪽은 바로 위 하나의 숫자만 받아 합을 구할 수 있습니다. 그 외 중간에 있는 숫자들은 양쪽 위 두 개의 숫자 중 큰 것을 받아 합을 구하면 됩니다. #include using namespace std; #define MAX 501 int DP[MAX][MAX]; int main(void) { int n; cin >> n; for (int i = 1; i temp; if (j == 1) DP[i][j] = temp +.. 2021. 3. 7. [백준/C,C++] 1149번: RGB거리 www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net DP 문제의 경우 점화식을 찾는 과정이 상당히 중요한데 이번 문제에서 점화식을 찾는데 꽤 애먹었습니다. 결국 다른 분들의 해답을 참고한 후 다시 제 식대로 코딩하게 되었습니다. 1번집 2번집 3번집 빨강색 비용 26 49 13 초록색 비용 40 60 89 파랑색 비용 83 57 99 빨강색 최소 비용 26 min(40, 83) + 49 = 89 min(86, 83) + 13 = 96 초록색.. 2021. 3. 7. [백준/C,C++] 9461번: 파도반 수열 www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net hackids.tistory.com/19 [백준/C,C++] 1904번: 01타일 www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이 hackids.tistory.com 1904번: 01타일 문제와 비슷하게 점화식만 찾는다면 쉽게 풀 수 있.. 2021. 3. 7. 이전 1 ··· 16 17 18 19 20 21 22 ··· 24 다음