본문 바로가기

알고리즘/백준 & swacademy108

BOJ 1701 - Cubeeditor (KMP, 실패함수) https://www.acmicpc.net/problem/1701 입력된 문자열에서 두 번 이상 나오는 부분 문자열의 길이중 최대를 출력하는 문제. abcabcabc 가 주어졌을 때, abc와 abcabc모두 가능하므로 둘 중 더 긴 abcabc의 길이인 6이 정답이다. 두 번 이상 나오는 부분 문자열의 길이 중 최대 -> 모든 부분 문자열 중에서 실패함수의 최대값 fail[n-1]까지 구하면서 인덱스0~1, 0~2, 0~3, ... 0~n-1 부분 문자열 중 실패함수를 모두 구할 수 있다. 따라서 시작지점이 0일때, 1일때, .... n-2일 때의 실패함수를 모두 확인해서 최대값을 출력하면 된다. #include #include #include using namespace std; const int M.. 2019. 11. 6.
SW 8568 - 3으로 나눈 순열 (발상) https://suuntree.tistory.com/75?category=797985 koi 모양정돈에서 썻던 논리와 같은 논리로 풀 수 있다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW1B8rJq3NUDFARC&categoryId=AW1B8rJq3NUDFARC&categoryType=CODE #include #include using namespace std; int main() { int testcase; cin >> testcase; for (int tc = 1; tc > n; for (int i = 1, input; i > input; if (input % 3 != i % 3) arr[i % 3][.. 2019. 11. 3.
BOJ 2450 - 모양 정돈 (KOI 중등 , 구현) https://www.acmicpc.net/problem/2450 최소한으로 이동하는 방법을 생각해 내지 못했다.. 정렬이 이뤄지면 결과적으로 6개의 가능한 모양이 있다. (1,2,3의 순열) 이 때 최소한으로 움직이는 방법을 살펴보면 1. 그룹(1)에 있는 그룹(2)(3)에 속해야 하는 요소들의 개수 (그룹(2),(3)에 속한 그룹(1)요소의 개수와 같다) (ex 입력이 1223111, (1,2,3)순서라면 2+1) 2. 그룹(2)에 있는 그룹(3)요소의 개수, 그룹(3)에 있는 그룹(2) 요소의 개수; 둘 중 큰 것 1,2를 더해주면 최소한으로 움직이는 횟수가 된다. 복잡해보이지만, 그룹1먼저 채워주고 그룹2,3을 생각해주는 것이다. 생각하는 과정에서 스쳐가듯 생각한 방법이긴 하지만, 이 방법이 유효.. 2019. 10. 17.
BOJ 14863 - 서울에서 경산까지 ( KOI 초등, knapsack ) https://www.acmicpc.net/problem/14863 딱봐도 냅색이라 바로 풀었는데.. int f(int k, int t) { if (k == N) return 0; //계산의 통일성을 위해서 f(n,양수) = 0 이라고 함. int& ret = dp[k][t]; if (ret != -1) return ret; ret = IMP; int time1 = opt[k].first.first, money1 = opt[k].first.second; int time2 = opt[k].second.first, money2 = opt[k].second.second; if (time1 2019. 10. 15.

티스토리툴바