개발새발

문제 링크 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 풀이 해당 문제는 A의 B제곱을 구해서 C로 나눈 나머지를 구하는 문제입니다. 얼핏 보면 간단해 보이는 문제이지만 범위가 굉장히 크죠 A, B, C 모두 2,147,483,647 이하의 자연수입니다. 그래서 만약 A의 2,147,483,647 제곱을 구하려면 많은 연산이 필요하고, 시간 복잡도가 올라가게 됩니다. 그럼 이 문제를 어떻게 풀어야 할까요?? 분할 정복과 DP로 풀면 되는데, 다음에 나오는 예를 같이 보며 이해해보겠습니다. 예를 들어 ..

문제 링크 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 문제 풀이 점화식 문제이고, 동적 프로그래밍 방법을 알면 쉽게 풀 수 있는 문제입니다. 차근차근 a1부터 써보면 값을 예측할 수 있습니다. a1 = 1; a2 = 2; a3 = a1 + a2 = 3; a4 = a2 + a3 = 5; ... 어떻게 이렇게 나오게 되는지 알아보겠습니다. 예를들어 a5의 경우를 보겠습니다. 1. a5는 맨 앞에 00이 오거나 1이 오게 됩니다. 2-1. 00이 오..