작심 24/7

10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net N값에 따른 계단의 수를 3까지 나타내 보면 i / j 1 2 3 4 5 6 7 8 9 1 1 2 3 4 5 6 7 8 9 2 10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98 3 101 121 123 210 212 232 234 321 323 343 345 432 434 454 456 543 545 565 567 654 656 676 678 765 767 787 789 876 878 898 987 989 1번째 일 때는 [i][1] = [i-1][j+1] + [i-2][1] 2번째부터 9번째까지는 [i][2]~[i][9] = [i-1]..

1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP로 1부터 N까지 차근차근 연산을 사용하는 횟수의 최솟값을 저장해나가면 된다. 1. 2의 배수일 경우 -> 2로 나눈 값의 횟수와 1을 뺀 값의 횟수를 구해 비교 뒤 저장 2. 3의 배수일 경우 -> 3으로 나눈 값의 횟수와 1을 뺀 값의 횟수를 구해 비교 뒤 저장 4. 나머지 경우 -> 1을 뺀 값의 횟수를 저장 문제에 나와있는 예제를 표로 표현해보면 이렇게 된다. N 횟수 1 0 2 1 + 최솟값(2/2의 횟수, 2-1의 횟수) = 1 3 1 + 최솟값(3/3의 횟수, 3-1의 횟수) = 1 4 1 + 최솟값(4/2의 횟수, 4-1의 횟수) = 2 5 1 + 5-1의 ..

2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 조건을 요약해보면 1. 1칸, 2칸만 이동할 수 있다. 2. 연속해서 1칸을 두 번 가는 것은 불가능하다. 3. N번째 칸은 무조건 밟아야 한다. 즉, i번째 칸에 있는 상태는 1칸 전을 밟고 온 상태 거나 2칸 전을 밟고 온 상태, 총 두 가지 경우가 나온다. 전자를 stair[0][i], 후자를 stair[1][i]라고 표현을 해본다면 stair[0][i]의 1칸 전은 stair[0][i-1]과 stair[1][i-1]이다. 그러나 1칸을 연속해서 이동할 수 없으므로 s..

1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최� www.acmicpc.net RGB거리와 마찬가지로 1번째부터 N번째까지 밑으로 내려가며 합이 최댓값이 되는 값만 저장한다. 문제에 있는 예제로 표현해보면 이렇게 최댓값인 30이 답이 되는 것이다. 이대로 구현해주면 끝 #include #include using namespace std; long long triangle[501][501] = { 0 }; int main() { int N; cin >> N >> triangle[0][0]; for (int ..

1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 처음엔 조건에 맞게 집을 칠할 수 있는 모든 경우의 수를 구해서 그 중 최솟값을 출력 해야하는줄 알았는데 만약에 그렇게 하면 3*(2^1000 -1)가지의 수가 나오게 된다. 절대 불가능한 숫자이므로 다시 다르게 생각해보았다. R G B 1번째 집을 R색으로 칠하려고 할 때 1번째 집을 G색으로 칠하려고 할 때 1번째 집을 B색으로 칠하려고 할 때 2번째 집을 R색으로 칠하려고 할 때 2번째 집을 G색으로 칠하려고 할 때 2번째 집을 B색으..

1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 순진하게 문제에 나와있는 대로 재귀를 해버리면 시간 초과 난다. 게다가 테스트 케이스 만큼 값을 여러 번 출력해야 하기 때문에 메모이제이션으로 풀어준다. N을 입력 받기 전에 미리 벡터에 0이 출력되는 횟수와 1이 출력되는 횟수를 저장시켜놓고 N을 받으면 거기서 바로 꺼내와 출력시키도록 하면 된다. #include #include using namespace std; int zero = 0, one = 0; vector fibonacci; int main() { fibonacci.push_back(pair(1, 0)); fibonacci.pu..

4150번: 피보나치 수 문제 피보나치 수열은 다음과 같이 그 전 두 항의 합으로 계산되는 수열이다. 첫 두 항은 1로 정의된다. f(1) = 1, f(2) = 1, f(n > 2) = f(n − 1) + f(n − 2) 정수를 입력받아, 그에 해당하는 피보나치 수를 www.acmicpc.net 정답이 1000자리 이하라는 말을 보고 눈을 의심했었다. int나 long long으로는 절대 풀 수 없기 때문에 string을 이용하여 답을 구했다. 계산할 때는 숫자를 뒤에서부터 한 자리씩 int로 바꾸어 계산 하였고 계산 완료된 값은 string형으로 배열에 넣어주었다. #include #include #include using namespace std; vector fibonacci; int main() ..