https://www.acmicpc.net/problem/11582 11582번: 치킨 TOP N 인하대 주변 치킨칩의 맛의 정도를 측정해 수치화하는 동아리 C.T.P(Chicken Tastes Perfect)의 회장 민호는 치킨집의 맛의 수치를 감소하지 않는 순으로 정렬을 하고 싶었다. 하지만 치킨집이 너무 많 www.acmicpc.net 정렬 문제. 현재 단계에서 K명이 정렬을 진행할때, 사람 혼자서 맡게되는 부분 배열의 크기는 N/K 이다. 전체 N개 크기의 배열을 N/K 개의 부분 배열로 분할해서, 그 부분만 정렬해주면 된다. 정렬에는 std::sort을 사용했다. #include using namespace std; int N,K; int arr[1234567] = {0}; int main(){..

https://www.acmicpc.net/problem/16943 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0 www.acmicpc.net 입력으로 들어오는 정수 A를 숫자가 아니라, '0' 부터 '9' 까지의 문자가 들어오는 문자열로 보면 이 문자열 배열에 대해서 next_permutation 을 통해서 순서를 섞어낼 때의 모든 조합을 구할 수 있다. 모든 순서를 찾아보는 시간복잡도는 O(N!) 이고, A는 10^9보다 작은 수이기 때문에 최대 9자리라서 N=9 이다. 이때의 계산 횟수는 대략 40만언저리쯤 ..

https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net DP로 해결했습니다. dp[i][j] 를 문자열 A를 i번 인덱스까지 자르고, 문자열 B를 j번 인덱스까지 잘랐을 때 두 문자열의 공통 접미사의 길이 로 정의한다. 이제 이 dp 배열을 O(N^2) 로 순회하면서 채우는데, 만일 A[i] 와 B[i]가 서로 같다면 A[i-1]과 B[i-1] 도 서로 비교해 보아야 한다. 이때, dp[i-1][j-1] 이 공통 접미사의 길이를 이미 저장하..

https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net DP 사용해서 해결했다. dp[i] 를 i일째 시점에서 상담을 끝냈을 때의 최대 이익으로 정의한다. i일째에 상담을 진행한 경우는 dp[i+T[i]] 를 dp[i] + P[i] 로 갱신 할 수 있으며, 이때 편의상 T[i]와 P[i] 를 0부터 시작하는 인덱스로 관리해주면 소스코드가 깔끔해진다. 상담을 진행하지 않더라도, 지난 일자에서의 최대 수익을 그대로 가져와서 ..

https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 바로 앞서 풀었던 문제와 동일한 유형 앞선 문제에서 태그를 까봤더니 플로이드-와샬이더라... arr[a][b] 를 a가 b 앞에 오는 사건인지 체크하는 용도로 사용한다. 플로이드 와셜을 통해서 모든 a,b 쌍들에 대해서 사건 간의 전후관계를 설정해 주고, 정답을 출력할 때 arr[a][b] 가 true라면 앞서는 것이고, arr[b][a] 가 true라면 뒤에 오는 사건인 것이고, 둘 다 ..

https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net DFS로 해결했다. 각 학생마다 DFS를 한번씩 돌면서 순회를 하는데, 이때 자기 자신을 포함해서 갈 수 있는 노드의 갯수를 세준다. 이 수에서 1을 뺀 것이 자기 자신보다 키가 큰 학생의 수이고, DFS 순회 과정에서 A에서 B로 갈수 있을경우 chk[B][A]에 기록해둔 뒤, 마지막에 chk[K] 배열 속의 모든 수들을 더해주고 1을 빼면 어떠한 위치에서 B로 올 수 있는 경우의 개수, 즉 자기..