🤔 PS(Problem Solving)/백준(BOJ)

[백준] 2193번 - 이친수

문제 문제0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.이친수는 0으로 시작하지 않는다.이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 N이 주어진다. 출력첫째 줄에 N자리 이친수의 개수를 출력한다. 풀이과정 (1)규칙DP이므로 점화식과 메모이제이션을 이용..

[백준] 11057번 - 오르막 수

문제 문제 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. 입력 첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다. 출력 첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다. 풀이과정 (1)규칙DP이므로 점화식과 메모이제이션을 이용합니다.첫째 자리수는 0~9맨 마지막 값은 1밖에 올 수 없습니다.오르막의 갯수는 10007로 나눈 나머지 입니다. (2)순서 n=3까지의 수를 만들어 봅니다. n..

[백준] 10844번 - 쉬운 계단 수

처음엔 문제가 이해가 안되서 단순히 1-9,2-17,3-32, 4-54 의 수열 규칙을 이용해서 문제를 풀려고 했는데 잘못된 접근이었다.~n일때까지 i번째 인덱스에서 만들수 있는 계단수갯수가 몇개인지를 계산하는 점화식을 만들어야 했다. 문제 문제45656이란 수를 보자.이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.) 입력첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 예제입력 -..

[백준] 9095번 - 1, 2, 3 더하기

문제 [9095번 링크]https://www.acmicpc.net/problem/9095 풀이과정 (1) 규칙 정수n의 1,2,3의 조합이 몇개 들어가는지 확인합니다. n=1 1 (1개) n=2 11,2 (2개) n=3 111,21,12,3 (4개) n=4 1111,112,121,211,22,13,31 (7개) n=5 11111,2111,1211,1121,1112,221,212,122,311,131,113,32,23 (13개) 이와같은 규칙으로 진행되므로, 점화식은 D[N] = D[N-1] + D[N-2] + D[N-3] 로 구할 수 있습니다.메모이제이션을 이용하여 해결합니다. (2) 순서 T와 정수n을 입력받고, 메모이제이션에 값을 저장하며 결과를 출력합니다. (3) 코드 #include #includ..

[백준] 11727번 - 2×n 타일링2

문제 문제2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×17 직사각형을 채운 한가지 예이다.입력첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)출력첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 풀이과정 (1) 규칙 2x2, 1x2, 2x1 타일이 몇개 들어가는지 확인합니다.(2x2는 4, 1x2는 2, 2x1는 1로 표기합니다) n=1 1 (1개) n=2 4,2,1(3개) n=3 41,14,21,12,111 (5개) n=4 (411,141,114,44)x2개 + 42,24,1111 (11개) n=5 (4111,1411,1141,1114,441,414,144)x2개 + 421,412,142,24..

[백준] 11726번 - 2×n 타일링

문제 문제2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.입력첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)출력첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 풀이과정 (1) 규칙 가로길이로만 계산하면 되기때문에 세로값 2는 신경쓰지 않습니다.(2는 (1x2 타일), 1은(2x1 타일) ) n=1 1 (1개) n=2 2,11 (2개) n=3 21,12,111 (3개) n=4 211,121,112,22,1111 (5개) n=5 2111,1211,1121,1112,221,212,122,11111 (8개) 이와같은 규칙으로 진행되므로, 점화식은..

[백준] 1463번 - 1로 만들기

여태까지 나는 코딩을 감으로만 또 막풀기만 한 것 같다.DP(Dynamic Programming)에서 제일 중요한 것이 점화식 세우기라는 것을 이제야 제대로 이해했다. 문제의 각 규칙을 공식으로 만들고, 이것을 하나의 수학식으로 만드는것이 점화식이었다.1463번 문제는 DP방법중 메모이제이션을 이용해서 풀면 최적화된 답이 나왔다. 내 코드 - 정답 못맞춤(점화식 사용X)#include using namespace std; long long c;vector v;long long minDiv(int N){ if (N 1); cout D[N] = D[N/2]+1 N-- -> D[N] = D[N-1]+1 */ memo[1] = 0;//1일때는 정답이므로 횟수X for (int i = 2; i

[백준] 입출력 문제 - 2557, 1000, 2558, 10950, 10951, 10952, 10953, 11021, 11022, 11718, 11719, 11720, 11721, 2741, 2742, 2739, 1924, 8393, 10818, 2438, 2439, 2440, 2441, 2442, 2445, 2522, 2446, 10991, 10992

2557번 – Hello world #include using namespace std; int main() { printf("Hello World!"); return 0; } 1000번- A+B, 2558번 - A+B2 #include using namespace std; int main() { int a, b; cin >> a >> b; cout a >> b; cout b) cout b; if (a == 0 && b == 0) break; else cout a >> c >> b; if (a + b == 0) break; else cout a >> b; cout

[백준] 1058번 - 친구

문제 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오. A와 B가 친구면, B와 A도 친구이고, A와 A는 친구가 아니다. 입력 첫째 줄에 사람의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 사람이 친구이면 Y, 아니면 N이 주어진다. (예제를 참고) 출력 첫째 줄에 가장 유명한 사람의 2-친구의 수를 출력한다. #언어 : ..