The Way

백준 온라인 저지(BOJ) 1131번 문제 https://www.acmicpc.net/problem/1131 1. 문제 요약 자연수 N이 주어졌을 때, N의 각 자리수를 K제곱한 뒤 더하여 수열을 만든다. A, B, K가 주어졌을 때, A≤N≤B의 N으로 시작하는 수열에서 가장 작은 수의 합을 구하기 2. 알고리즘 쉬워보이는데 생각보다 까다롭다. 다이나믹 프로그래밍 문제인데, A->B일 때 A로 시작하는 수열의 최솟값 = B로 시작하는 수열의 최솟값 / A 중 작은 값 이 성립한다. 모든 수열은 최종적으로 루프에 도달하게 되는데, 시간관계상 이 루프의 정보들만 미리 구한 뒤 넣어주었다. 합이 10억을 가뿐히 넘기므로 long long을 써야한다. 3. 코드 #include using namespace s..

백준 온라인 저지(BOJ) 2959번 문제https://www.acmicpc.net/problem/2959 1. 문제 요약숫자 4개가 주어졌을 때(순서 무관) 그 숫자만큼 이동 후 오른쪽으로 90도 회전하여 만들어지는 직사각형의 최대 넓이는? 2. 알고리즘직사각형은 변 2개가 있어야 만들어진다.작은 것 / 큰 것이 있을 때 작은 것의 길이만큼이 해당 변의 길이가 된다. A ≤ B ≤ C ≤ D로 있으면 이 때 가능한 값은 AB or AC이므로 최대 넓이는 AC이다. 3. 코드 #include #include using namespace std; int main() { int arr[4]; cin >> arr[0] >> arr[1] >> arr[2] >> arr[3]; sort(arr, arr + 4); ..

백준 온라인 저지(BOJ) 1904번 문제 https://www.acmicpc.net/problem/1904 1. 문제 요약 타일 두 종류가 있는데, 하나는 00, 하나는 1이다. 두 종류의 타일을 가지고 길이 N짜리 타일을 만들 수 있는 경우의 수를 구하시오. 2. 알고리즘 기본적인 다이나믹 프로그래밍 문제. 피보나치 수열이 나온다. 3. 코드 #include using namespace std; int main() { int N; cin >> N; int a = 0, b = 1, c; for (int i = 0; i < N; ++i) { c = (a + b) % 15746; a = b; b = c; } cout

백준 온라인 저지(BOJ) 9095번 문제https://www.acmicpc.net/problem/9095 1. 문제 요약정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수 구하기 2. 알고리즘기본적인 다이나믹 프로그래밍 문제.특정 항의 값은 앞의 세 항을 더한 값이 된다. switch문을 한 번 써봤다 3. 코드 #include using namespace std; int main() { int T; cin >> T; for (int i = 0; i > N; switch (N) { case 1: cout

백준 온라인 저지(BOJ) 7770번 문제 https://www.acmicpc.net/problem/7770 1. 문제 요약 안정적인 피라미드란 블럭의 아래에 있는 블럭의 모든 면이 땅이나 다른 블럭과 접할 때, 안정적이라고 한다. 블럭의 개수가 주어질 때 그 블럭으로 만들 수 있는 안정적인 피라미드의 최대 높이를 구하기 2. 알고리즘 특정 높이의 안정적인 피라미드의 최소 개수는 정해진다. 점화식을 따르는데, 2계차수열을 따른다. 조금만 계산해보면 일반항을 구할 수 있다. 높이 N 최소 개수 > n; int h = 0; int block = 0; while (block

백준 온라인 저지(BOJ) 11726번 문제 https://www.acmicpc.net/problem/11726 1. 문제 요약 2 x n의 타일을 1 x 2 가로 or 세로 모양 타일로 채우는 방법의 수 구하기 2. 알고리즘 기본적인 다이나믹 프로그래밍이다. 피보나치 수열이 나온다. 설명은 생략. 3. 코드 #include using namespace std; int main() { int n; cin >> n; int a = 0, b = 1, c; for (int i = 0; i < n; ++i) { c = (a + b) % 10007; a = b; b = c; } cout

백준 온라인 저지(BOJ) 13623번 문제https://www.acmicpc.net/problem/13623 1. 문제 요약A, B, C 3명이서 0 아님 1을 말하는데, 혼자만 다른 숫자를 말할 때 이긴다이긴 사람을 출력, 이긴 사람이 없으면 * 출력 2. 알고리즘if문이 가장 빠른 듯 3. 코드 #include using namespace std; int main() { int a, b, c; cin >> a >> b >> c; if (a == 1 && b == 0 && c == 0) printf("A\n"); else if (a == 0 && b == 1 && c == 1) printf("A\n"); else if (a == 0 && b == 1 && c == 0) printf("B\n"); el..

백준 온라인 저지(BOJ) 9664번 문제https://www.acmicpc.net/problem/9664 1. 문제 요약재산(금메달)을 N명의 딸들이 분배막내 딸이 최대 1 차이가 나도록 나눈 뒤 그 중 적은 것을 가져가는데(예를 들어서 14개였고 3명이면 5/5/4로 나누고 4를 가져감)가져간 이후 남은 개수를 보고 가능한 원래 개수의 최댓값/최솟값을 맞추기 (cunning daughter인데 왜 적은 거를 가져가는지 잘 모르겠다.. cunning의 뜻은 '교활한'인데..) 2. 알고리즘원래 개수는 하나로 결정되거나 1 차이가 나게 된다남은게 똑같이 분배되지 않을 경우 (ex 5/5/4)으로 남았으면 적은 것을 가져갔으므로 작은 값을 더해준게 원래 값남은게 똑같이 분배될 경우 (ex 5/5/5) 막내..

백준 온라인 저지(BOJ) 4881번 문제https://www.acmicpc.net/problem/4881 1. 문제 요약각 자리수를 제곱하여 더하여 만들어지는 수열이 있다.초기 숫자 두 개가 주어질 때, 같은 숫자가 나올 때까지의 수열의 길이의 합이 가장 작을 때 그 합은 얼마인가? 2. 알고리즘문제에서 두 개의 사이클이 소개되었다.하나는 89, 145, 42, 20, 4, 16, 37, 58이고 하나는 1이다.따로 계산을 해보면 알겠지만 이 두 개의 사이클이 유일한 사이클이다. 따라서 수열이 저 사이클에 포함될 때 까지 계산해준 뒤,서로 다른 사이클이면 불가능같은 사이클일 경우, 첫 도착지점이 같으면 공통 부분을 소거해주고첫 도착지점이 다를 경우 (ex 89, 37처럼 될 경우) 짧은 방향으로 사이클..

백준 온라인 저지(BOJ) 2606번 문제https://www.acmicpc.net/problem/2606 1. 문제 요약컴퓨터 간 연결 정보들이 주어질 때,1번 컴퓨터를 통해 바이러스에 감염되는 컴퓨터의 수를 구하기 2. 알고리즘간단한 형태의 탐색 문제이다.마지막에 합을 더해줄 때 1번 컴퓨터는 제외하고 더해줘야 한다는 점에 주의.여러 효율적인 방법이 있겠지만... 역시 속도가 생명.. 3. 코드 #include #include #include using namespace std; int main() { vector connect[100]; int inf[100] = { 0 }; int N, M; scanf("%d %d", &N, &M); int t1, t2; for (int i = 0; i < M; ..