위 이미지와 같이 P(N)의 값이 증가한다고 할 때 P(N)의 값을 출력한다. P(N)의 값은 1 1 1 2 2 3 4 7 9 12 ... 순서로 증가한다.
테스트 케이스
5 1 5 6 12 100
1 2 3 16 888855064897
문제 풀이
위 이미지에서 색칠이 된 선분을 보면 직전 삼각형과 5번째 이전 삼각형의 변 길이의 합이라는 것을 알 수 있다. 즉, f(n) = f(n - 1) + f(n - 5)라는 규칙을 갖는다. 점화식으로 [0] ~ [4]까지 1, 1, 1, 2, 2를 넣어주고 [5] ~ [100]까지 수열을 구해준 이후 테스트 케이스에 해당하는 결과값을 출력해주면 된다. 결과 값이 최대 88억까지 나올 수 있으므로 수열의 기본 자료형은 64bit 이상으로 하여야 한다.
풀이 코드
#include <iostream>
using namespace std;
void BAEKJOON_9461()
{
int T;
cin >> T;
uint64_t sequence[100] = { 1, 1, 1, 2, 2, };
for (int i = 5; i < 100; ++i)
{
sequence[i] = sequence[i - 1] + sequence[i - 5];
}
for (int i = 0; i < T; ++i)
{
int pn;
cin >> pn;
cout << sequence[pn - 1] << "\n";
}
return;
}
f(4)에 대해 구한다고 할 경우 아래와 같이 구할 수 있다. 1. 1로 시작하는 숫자는 1xxx가 된다. xxx는 f(4)일 때의 가짓수가 동일하다. 2. 00으로 시작하는 숫자는 00xx가 된다. xx는 f(3) 일 때의 가짓수와 동일하다. 3. f(5)의 가짓수는 1로 시작하는 숫자와 00으로 시작하는 숫자의 가짓수를 합한 것과 동일하다. - f(5) = f(4) + f(3) 즉, 이 문제는 점화식이 1, 2인 피보나치 수열이다. 함수 구현은 피보나치 수열을 구현하듯이 하면 된다.
다만 결과 출력이 15746으로 나눈 나머지이고, 나머지 연산의 법칙상 (a % m + b % m) % m은 성립이 되므로# 피보나치 수열을 구하는 과정에서 각 수를 15746으로 나눈 나머지로 계산하여야 올바른 값을 얻을 수 있다.
풀이 코드
#include <iostream>
using namespace std;
void BAEKJOON_1904()
{
int N;
cin >> N;
int f1 = 1;
int f2 = 2;
int f3;
if (N <= 2)
{
f3 = N == 1 ? 1 : 2;
}
else
{
for (int i = 3; i <= N; i++)
{
f3 = (f2 + f1) % 15746;
f1 = f2 % 15746;
f2 = f3;
}
}
cout << f3 << endl;
return;
}
n을 입력 받아 위 함수를 실행하였을 때 0이 출력되는 횟수와 1이 출력되는 횟수를 출력한다.
테스트 케이스
3 0 1 3 40
1 0 0 1 1 2 63245986 102334155
문제 풀이
하나의 결과를 출력하는데 소요되는 시간은 얼마 걸리지 않지만, T회의 테스트케이스를 진행하는 과정에서 매번 계산을 새로 하게 될 경우 그만큼 연산을 낭비하게 된다.
n이 입력되는 경우 0이 출력된 횟수는 n-1번째 피보나치 수와 동일하고, 1이 출력된 횟수는 n번째 피보나치 수와 동일하다. 따라서 n번째까지의 피보나치 수를 구하면 각각의 결과를 파악할 수 있다.
다만 T개의 테스트 케이스를 수행하는 것이 이번 문제의 특징이고, 첫 번째 테스트 케이스로 n이 입력된 경우 1~n까지의 결과가 40을 구하는 과정에서 이미 구해지게 되므로, 이들에 대한 정보를 별도로 저장하여 다른 테스트 케이스에서 활용한다면 연산 낭비를 줄일 수 있다. n보다 작은 수인 경우에는 바로 결과가 나오고, n보다 큰 수는 n번째까지의 연산 과정을 생략할 수 있기 때문이다.
1. [0]~[40]까지를 저장할 수 있도록 배열을 생성한다. 2. [0] = 0, [1] = 1로 대입한다. 3. n을 입력받는다. 4. 2~n까지 진행하면서 [i] == 0인 경우에는 [i] = [i - 1] + [i - 2]를 대입한다. 아닌 경우에는 다음으로 넘어간다. 5. 0 호출 횟수와 1 호출 횟수를 출력한다. 6. T회동안 3~5를 반복한다.
풀이 코드
#include <iostream>
using namespace std;
void BAEKJOON_1003()
{
int T;
cin >> T;
int fib[41] = { 0 };
fib[0] = 0;
fib[1] = 1;
for (int i = 0; i < T; ++i)
{
int n;
int callZero;
int callOne;
cin >> n;
if (n == 0)
{
callZero = 1;
callOne = 0;
}
else if (n == 1)
{
callZero = 0;
callOne = 1;
}
else
{
for (int i = 2; i <= n; ++i)
{
if (fib[i] == 0)
{
fib[i] = fib[i - 1] + fib[i - 2];
}
}
callZero = fib[n - 1];
callOne = fib[n];
}
cout << callZero << " " << callOne << endl;
}
return;
}
입력 범위인 90번째의 수가 매우 크므로 결과 출력에는 64bit 변수가 필요하다. 피보나치 수열의 경우 f(n-1) + f(n-2)로 표현되는 것이 일반적이지만 이를 재귀함수로 구현할 경우 같은 중복 계산이 매우 많아지므로 수가 커질수록 성능이 크게 저하된다. 차라리 for를 이용한 반복문을 이용하는 편이 빠르다.
동적 계획법으로 풀 경우에는 해당하는만큼 배열을 생성하고 아래와 같이 진행하면 된다. 1. n + 1개짜리 배열을 생성하고 [1]과 [2]에는 각각 1을 대입한다. 2. [2]~[n]까지 [n-1], [n-2]를 합한 수를 대입한다. 3. n번째 값을 출력한다.
풀이 코드
#include <iostream>
using namespace std;
// 동적 계획법
void BAEKJOON_2748()
{
uint64_t n;
cin >> n;
if (n == 1 || n == 2)
{
cout << 1 << endl;
}
else
{
uint64_t* fib = new uint64_t[n];
fib[0] = 1;
fib[1] = 1;
for (int i = 2; i < n; i++)
{
fib[i] = fib[i - 1] + fib[i - 2];
}
cout << fib[n - 1] << endl;
delete[] fib;
}
return;
}
나이와 이름순으로 입력받은 N의 멤버 정보를 나이순으로 정렬하여 출력한다. 나이가 동일한 경우에는 먼저 입력받은 순서대로 출력한다.
테스트 케이스
3 21 Junkyu 21 Dohyun 20 Sunyoung
20 Sunyoung 21 Junkyu 21 Dohyun
문제 풀이
나이는 1~200까지의 범위이고, 같은 나이일 경우 입력받은 순서대로 출력하므로 나이 입력 범위에 해당하는 인덱스 배열을 만든 후 해당 인덱스에 입력받은 이름들을 추가해주는 방식으로 풀면 된다. C++ 같은 경우에는 vector가 이러한 방식으로 풀기에 용이하다. key의 중복 입력을 허용하는 multimap을 이용해 풀 경우에는 반복자를 이용해 바로 출력해주면 된다. 다만 이 경우 vector보다 느리고 메모리 사용량이 많다는 단점이 있다.
풀이 코드
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// vector를 이용한 방법
void BAEKJOON_10814()
{
int N;
cin >> N;
vector<string> member[201];
for (int i = 0; i < N; ++i)
{
int age;
string name;
cin >> age >> name;
member[age].push_back(name);
}
for (int i = 0; i < 201; ++i)
{
for (auto it = member[i].begin(); it != member[i].end(); ++it)
{
cout << i << " " << *it << "\n";
}
}
return;
}
#include <iostream>
#include <map>
#include <string>
using namespace std;
// multimap을 이용한 방법
void BAEKJOON_10814()
{
int N;
cin >> N;
multimap<int, string> member;
for (int i = 0; i < N; ++i)
{
int age;
string name;
cin >> age >> name;
member.insert(pair<int, string>(age, name));
}
for (auto it = member.begin(); it != member.end(); ++it)
{
cout << it->first << " " << it->second << "\n";
}
return;
}
입력받은 N개의 문자를 길이가 짧은 순서대로 출력한다. 길이가 동일할 경우 사전순으로 출력한다. 단, 같은 단어를 한 번만 출력한다.
테스트 케이스
13 but i wont hesitate no more no more it cannot wait im yours
i im it no but more wait wont yours cannot hesitate
문제 풀이
문제에서 제시한 규칙에 맞춰 algorithm의 sort 함수에 사용할 비교용 함수를 만들면 된다. 비교용 함수를 만들기 싫다면 문자열 길이별로 묶어서 각 길이마다 sort 하는 방식을 사용해도 된다. 출력 시에는 현재 문자열과 이전 or 다음 문자열과 비교하여 동일하지 않으면 출력하도록 한다.
풀이 코드
#include <iostream>
#include <iostream>
#include <string>
using namespace std;
// 비교함수를 만들어서 sort 하는 경우
bool cmp_1181(const string& left, const string& right)
{
if (left.length() == right.length())
{
return left < right;
}
return left.length() < right.length();
}
void BAEKJOON_1181()
{
int N;
cin >> N;
string* word = new string[N + 1];
for (int i = 0; i < N; ++i)
{
cin >> word[i];
}
sort(word, word + N, cmp_1181);
for (int i = 0; i < N; ++i)
{
if (word[i] == word[i + 1])
{
continue;
}
cout << word[i] << "\n";
}
delete[] word;
return;
}
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// length별로 그룹을 나눈 후 sort 하는 경우
void BAEKJOON_1181()
{
int N;
cin >> N;
string word;
vector<string> wordList[51];
for (int i = 0; i < N; ++i)
{
cin >> word;
wordList[word.size()].push_back(word);
}
for (int i = 0; i < 51; ++i)
{
sort(wordList[i].begin(), wordList[i].begin() + wordList[i].size());
for (auto it = wordList[i].begin(); it != wordList[i].end(); ++it)
{
if (it != wordList[i].begin())
{
if (*it == *(it - 1))
{
continue;
}
}
cout << *it << "\n";
}
}
return;
}
