Memo
어려웠던 점
K가 만약에 10 이라고 한다면, 21C10 = 352716 이고 (5개의 알파벳은 이미 확정적이므로 21임) N의 최대값인 50과 길이의 최대값인 7 (양 옆을 제거하면 7이 최대) 을 모두 곱하면 123450600(1억이 넘음) 이라는 숫자가 나오는데, 이는 1초만에 계산을 끝낼 수 있는 연산량이 아니라고 생각이 들었기 때문에 코드를 작성하기 망설여 졌습니다.
우선 1억 언저리 이므로 코드를 작성해 봅니다.
처음 시간 초과가 났던 코드
#include <iostream>
#include <vector>
#include <algorithm>
std::vector<std::string> words;
std::vector<int> check;
int N, K, ans;
void input_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
int alpha_to_index(char ch)
{
return (ch - 'a');
}
void input()
{
input_faster();
std::cin >> N >> K;
words.resize(N);
size_t _N = N;
for (size_t i = 0 ; i < _N ; i++)
std::cin >> words[i];
check.resize(26, 0);
ans = 0;
check[0] = 1;
check[2] = 1;
check[8] = 1;
check[13] = 1;
check[19] = 1;
}
std::string parsing(std::string a)
{
std::string rtn;
for (size_t i = 4 ; i < a.size() - 4; i++)
rtn.push_back(a[i]);
return (rtn);
}
int main_logic()
{
size_t cnt;
int rtn = 0;
for (size_t i = 0 ; i < N ; i++)
{
cnt = 0;
for (size_t j = 0 ; j < words[i].size(); j++)
{
if (!(check[alpha_to_index(words[i][j])]))
break;
cnt++;
}
if (cnt == words[i].size())
rtn++;
}
return (rtn);
}
void backtracking(int depth)
{
if (depth == K)
{
int val = main_logic();
ans = std::max(val, ans);
return ;
}
for (size_t i = 0 ; i < 26 ; i++)
{
if (!check[i])
{
check[i] = 1;
backtracking(depth + 1);
check[i] = 0;
}
}
}
void solve()
{
if (K < 5)
return ;
K -= 5;
for (size_t i = 0 ; i < words.size(); i++)
words[i] = parsing(words[i]);
backtracking(0);
}
void print_val()
{
std::cout << ans;
}
int main()
{
input();
solve();
print_val();
return (0);
}
C++
복사
위 코드의 문제점은
for (size_t i = 0 ; i < 26 ; i++)
{
if (!check[i])
{
check[i] = 1;
backtracking(depth + 1);
check[i] = 0;
}
C++
복사
바로 이 부분이었는데, 이 코드의 경우는 예를 들어 BCD, BDC를 각각의 경우로 계산한다는 점이었습니다. 따라서 이는 조합 코드가 아니기 때문에 코드를 다음과 같이 수정했습니다.
for (size_t i = x ; i < 26 ; i++)
{
if (!check[i])
{
check[i] = 1;
backtracking(i + 1, depth + 1);
check[i] = 0;
}
}
C++
복사
Code
제출 날짜
@3/7/2021
메모리
2020 KB
시간
128 ms
#include <iostream>
#include <vector>
#include <algorithm>
std::vector<std::string> words;
std::vector<int> check;
int N, K, ans;
void input_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
int alpha_to_index(char ch)
{
return (ch - 'a');
}
void input()
{
input_faster();
std::cin >> N >> K;
words.resize(N);
size_t _N = N;
for (size_t i = 0 ; i < _N ; i++)
std::cin >> words[i];
check.resize(26, 0);
ans = 0;
check[0] = 1;
check[2] = 1;
check[8] = 1;
check[13] = 1;
check[19] = 1;
}
std::string parsing(std::string a)
{
std::string rtn;
for (size_t i = 4 ; i < a.size() - 4; i++)
rtn.push_back(a[i]);
return (rtn);
}
int main_logic()
{
size_t cnt;
int rtn = 0;
for (size_t i = 0 ; i < N ; i++)
{
cnt = 0;
for (size_t j = 0 ; j < words[i].size(); j++)
{
if (!(check[alpha_to_index(words[i][j])]))
break;
cnt++;
}
if (cnt == words[i].size())
rtn++;
}
return (rtn);
}
void backtracking(int x, int depth)
{
if (depth == K)
{
int val = main_logic();
ans = std::max(val, ans);
return ;
}
for (size_t i = x ; i < 26 ; i++)
{
if (!check[i])
{
check[i] = 1;
backtracking(i + 1, depth + 1);
check[i] = 0;
}
}
}
void solve()
{
if (K < 5)
return ;
K -= 5;
for (size_t i = 0 ; i < words.size(); i++)
words[i] = parsing(words[i]);
backtracking(0, 0);
}
void print_val()
{
std::cout << ans;
}
int main()
{
input();
solve();
print_val();
return (0);
}
C++
복사
과연 조합으로 풀 경우 시간 초과가 안날까..?
문제는 풀었지만, 시간 복잡도에 대한 의문이 있었습니다.
위 링크에서 똑같은 의문을 제기하고 있었는데, 정리해 보자면 시간복잡도를 계산한 결과 1억 언저리면 백준 기준으로 통과할 것으로 보입니다.
