본문 바로가기

c104

[백준/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.
[백준/C,C++] 1904번: 01타일 www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 점화식만 찾아낸다면 정말 간단한 문제입니다. N이 0일 경우 만들 수 있는 타일의 개수는 0개입니다. 1일 경우 1개, 2일 경우 2개라고 문제에 나와 있죠. 3은 011, 100, 111로 3개입니다. 4의 경우는 5개로 문제에 나와 있습니다. 해를 쭉 나열해보면 0, 1, 2, 3, 5인데, 피보나치 수열과 굉장히 유사합니다. 작은 문제를 쌓아 큰 문제를 푸는 상향식(Bottom-up) 동적 계획법을 이용하면 쉽.. 2021. 3. 7.

티스토리툴바