Jubil의 프로그래밍 블로그

10844_쉬운 계단 수 링크 https://www.acmicpc.net/problem/10844 풀이 잠깐 생각해보면, n-1까지의 계단 수에 어떤 걸 더해서 n까지의 계단 수의 경우의 수를 구할 수 있을 것 같지만 조건이 부족합니다. 계단 수는 마지막 자리의 숫자로 그 다음 자리의 숫자가 뭐가 될지 결정됩니다. 다음 자리의 숫자가 3이 되려면 -1과 +1인 2, 4가 마지막 숫자여야 됩니다. 보통 이렇게 2가지를 갖지만 0과 9는 각각 1과 8가 마지막 자리일 때 가지게 됩니다. 이러한 특성 때문에 계단 수의 경우의 수를 구하기 위해서는 마지막 자리의 어떤 숫자가 몇 개씩 있는지 알아야만 합니다. n은 1

1932_정수 삼각형 링크 https://www.acmicpc.net/problem/1932 풀이 우선 어떤 정수로 올 수 있는 방법을 알아봅시다. 양 끝 대각선에 있는 정수로 올 수 있는 방법은 단 한 가지입니다. 이렇게 말이죠. 그럼 양 끝 대각선에 있는 정수가 아닌 경우에는 어떤 방법이 있을까요? 어떤 정수를 잡던지 방법은 왼쪽 위와 오른쪽 위 두 가지 방법이 있을 것입니다. 그렇다면 어떠한 정수로 오는 경로의 합의 최댓값을 구해줘서 저장해 놓으면 되겠네요. 그림으로 설명하겠습니다. 이렇게 두 선택지 중 더 큰 쪽에서 오는 걸로 선택해 더해주면 됩니다. 삼각형의 크기 n은 1

9095_1, 2, 3 더하기 링크 https://www.acmicpc.net/problem/9095 풀이 정수 n을 1, 2, 3의 조합으로 나타내는 방법을 찾아야 합니다. 그 방법은 n-1까지의 조합 + 1과 n-2까지의 조합 + 2와 n-3까지의 조합 + 3이 있을 것입니다. 4를 1, 2, 3의 조합으로 나타내는 방법을 위를 통해 구해보면, n-1까지의 조합 -> 3까지의 조합 1 + 1 + 1 + 1 1 + 2 + 1 2 + 1 + 1 3 + 1 n-2까지의 조합 -> 2까지의 조합 1 + 1 + 2 2 + 2 n-3까지의 조합 -> 1까지의 조합 1 + 3 이렇게 7가지가 됩니다. 점화식을 세워보면 DP[n] = DP[n-1] + DP[n-2] + DP[n-3] (n >= 4) 이 됩니다. D..

11727_2xn 타일링 2 링크 https://www.acmicpc.net/problem/11727 풀이 점화식을 세우기 위해서 그림을 그려보겠습니다. 이렇게 되어 2*n까지 타일을 채우는 방법은 f(n-1) + 2*f(n-2)라는 것을 알 수 있습니다. 점화식은 DP[n] = DP[n-1] + 2*DP[n-2]입니다. DP[1]과 DP[2]는 미리 구해 놓아야 합니다. 코드로 구현하겠습니다. 주의할 점은 n은 1000까지 -> 배열은 1001로 선언, 출력은 10,007로 나눈 나머지로 해야 합니다. 코드

11726_2xn 타일링 링크 https://www.acmicpc.net/problem/11726 풀이 점화식을 세우기 위해서 그림을 그려보겠습니다. 이렇게 되어 2*n까지 타일을 채우는 방법은 f(n-1) + f(n-2)라는 것을 알 수 있습니다. 점화식은 DP[n] = DP[n-1] + DP[n-2]입니다. DP[1]과 DP[2]는 미리 구해 놓아야 합니다. 코드로 구현하겠습니다. 주의할 점은 n은 1000까지 -> 배열은 1001로 선언, 출력은 10,007로 나눈 나머지로 해야 합니다. 코드

1152_단어의 개수 링크 https://www.acmicpc.net/problem/1152 풀이 이 문제는 생각보다 정답 비율이 낮습니다. 단어는 공백으로 구분할 수 있고 공백이 연속해서 나오는 경우는 없다고 했기 때문에, 공백의 개수 + 1이 단어의 개수라는 것을 알 수 있습니다. 하지만 맨 앞에 공백이 오거나 맨 뒤에 공백으로 끝나는 경우가 있을 수도 있으니 그 부분에 대한 코드도 짜줘야 할 것 같습니다. 코드

14584_암호 해독 링크 https://www.acmicpc.net/problem/14584 풀이 1) 문자열을 1씩 올리면서 문자열에 주어진 단어들이 있는지 탐색합니다. 2) 있으면 문자열을 출력하고 종료. 문자열 탐색 방법 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 //14584_암호 해독 #include #include using namespace std; int main() { int n, i, j; string str; //암호 문자열 string word[20]; //단어 cin >> str; cin >> n; for (i = 0; i > word[i]; } for (i = 0; i

10250_ACM 호텔 링크 https://www.acmicpc.net/problem/10250 풀이 일단 이렇게 사람들이 배정을 받는다는 사실은 눈치 챘을 것입니다. 단순하게 예제만 본다면 402의 4는 10%6이고 뒤에 2는 10/6+1이고, 1203의 12는 72%30이고, 3은 72/30+1이라고 생각할 수 있습니다. 이렇게 생각했을 때 일반화 한다면, h, w, n을 받았을 때, n%h과 n/h+1을 출력하면 될 것 같습니다. 하지만 이 문제에서 주의할 게 2가지 있습니다. 1) 꼭대기 층일 때 (n%h가 0일 때) 이때는 값이 다르게 됩니다. 2) 출력할 때, YXX, YYXX로 출력해야 하는데 X가 한 자리이면 앞에 0을 붙여야한다. ex) 1층 1호 -> 11(X) 101(O) 이것만 주의..

1193_분수찾기 링크 https://www.acmicpc.net/problem/1193 풀이 규칙을 찾아보면 이렇게 된다는 것을 알 수 있습니다. 군수열처럼 이렇게 두고, 군(i)과 항(offset)을 찾아내서 풀면 됩니다. 홀수 군일 때는 i에서 offset을 뺀 것/offset + 1이고, 짝수 군일 때는 그 반대로 출력하면 됩니다. offset은 n에서 min을 빼서 구할 수 있습니다. 코드