백준알고리즘7 [BOJ/C++]1699번 제곱수의 합 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 문제 자연수 n을 $11=2^2+2^2+1^2+1^2+1^2$ 혹은 $11=3^2+1^2+1^2$와 같은 제곱수들의 합으로 나타낼 수 있다. 이때 표현할 수 있는 제곱수 항의 최소 개수를 구해라. 풀이 i가 제곱수로 표현가능한 경우, 즉 i=j*j인 경우는 dp[i]가 1이다. 그 경우 dp[i]에 1을 넣어주고, 그 외에 경우에는 일단 dp[i]=dp[i-.. 2020. 8. 18. [BOJ/C++]9465번 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티 www.acmicpc.net 문제 스티커 2n개를 구입했다. 스티커는 2xn 행렬로 배치되어 있다. 서로 변을 공유하는 스티커는 뗄 수 없는 조건에서 스티커 점수 합의 최대값을 구해라. 풀이방법 처음에 엄청 어렵게 생각해서 헤맸던 문제. 문제 풀이의 핵심은 이렇다. 이전 column의 스티커는 더하지 않을 수 있다. 어차피 최댓값을 구하는 문제면 2칸 이상 건너지 않는다. 따라서 i번째 column에서는 "i-1 column에서.. 2020. 7. 29. [BOJ/C++]2193번 이천수 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 이진수 중 1이 연속으로 들어오지 않고 1로 시작하는 수를 이천수라 한다. 예를들어 1001이나 1010은 이천수지만, 1101이나 10110은 이천수라 할 수 없다. n자리수(1n; long dp[n+1][2]; dp[1][0]=1;dp[1][1]=1; for(int i=2;i 2020. 7. 29. [BOJ/C++]11057번 오르막 수 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수� www.acmicpc.net 문제 '2234', '3678', '11119'와 같이 인접한 수가 같거나 오름차순인 수를 "오르막 수"라고 한다. n길이의 오르막 수 개수를 구해라. 풀이방법 https://lionontheshore.tistory.com/33?category=929275 [BOJ/C++]10844 번 쉬운 계단 수 https://www.acmicpc.net/problem/1.. 2020. 7. 29. [BOJ/C++]10844 번 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 계단 수는 '45656'과 같이 인접한 모든 자리 수가 1씩 차이나는 수이다. 길이가 n인 계단수가 총 몇개인지 구해라. 풀이방법 앞서 풀었던 DP문제와 마찬가지로 점화식을 구해 풀어준다. 다음과 같이 n번째 자릿수부터 아래로 내려가며 가능한 계단수를 구해준다. i가 1부터 8까지는 뒤에 i-1, i+2가 올 수 있고, i가 0이면 1, 9면 8만 뒤에 올 수 있다. 마지막에 n번째 자릿수의 1~9가 가지는 경우의 수를 다 더해주면 총 경우의 수를 구할 수 있다. 먼저 dp[i번째 자릿수][i번째 자리의 .. 2020. 7. 29. [BOJ/C++]11726번 2xn 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net dp를 이해하고 나니 한결 쉽게 풀 수 있었던 문제. 바보같이 10007의 나머지를 구하라는 조건을 못 보고 계속 틀렸습니다 나와서 열났던 문제이다. 문제 사용자로부터 n을 입력받고, 2xn크기의 직사각형을 만든다. 이 직사각형에는 2x1또는 1x2타일이 들어갈 수 있다. 2xn 크기의 직사각형에 타일이 들어가는 경우의수를 구해라. 풀이방법 이 문제는 점화식으로 풀 수 있다. 2x1과 1x2의 타일은 i번째 직사각형에.. 2020. 7. 28. 이전 1 2 다음
