https://www.acmicpc.net/problem/17299 문제의 특성상 수열을 각 수열의 숫자가 등장한 횟수로 치환한 수열로 나타냈을 때, 내림차순의 형태를 띌 것이다.이때, 오름차순으로 바뀌는 지점의 값 K가 있다면, 이전 숫자들 중 K보다 작은 숫자의 오등큰수는, 등장 횟수를 치환한 수열을 다시 F(x)라고 한다면 F(K)가 될 것이다.이를 이용하여 Stack으로 문제를 해결할 수 있다. #include #define fastio std::ios_base::sync_with_stdio(false);\cin.tie(NULL)using namespace std;using ll = long long;using pii = pair;using tiii = tuple;int dx[4] = { -1,1..
https://www.acmicpc.net/problem/10711 Brute하게는 100만개의 8방을 매번 검사하여 찾을 수 있다.하지만 모래성이 하나하나 꺼지는 경우를 생각하면, 시간복잡도에서 뻑이 날 것이다.따라서, 이를 줄이는 부분이 필요하고, 모래성이 꺼질 때만 그 주변의 모래성을 검사하면 된다는 아이디어로 최적화를 할 수 있었다. BFS와 Level Queue 테크닉을 사용하여 문제를 해결했다. #include #define fastio std::ios_base::sync_with_stdio(false);\cin.tie(NULL)using namespace std;using ll = long long;using pii = pair;using tiii = tuple;int dx[3] = { 0,..
https://www.acmicpc.net/problem/14391 시간복잡도는 Brute하게 0,0을 시작 지점으로 잡으면 처음 만들 수 있는 종이조각 갯수 7, 다음 0,1 은 6, 다음 5 .....이런식으로 16개 자리에 대해 계산해보면 1,741,824,000 이 나온다.이 값이 Brute하기도 하고, 문제 제한 시간이 2초이므로, 20억 이내로 Safe이다. 풀이의 DFS는 X++ 방향으로 나아가며, X가 가로 범위를 넘어설 때, Y를 증가시킨다.이때 DFS의 반환값은 현재 Board의 위치에서 X++, Y++ 방향으로 신장하여 만들 수 있는 모든 종이조각에 대하여, 그 이후에 만들 수 있는 다른 모든 종이조각의 합 중 최댓값이다.이를 구현하기 위해, BackTracking을 사용했다.#inc..
