세그먼트 트리13 백준 3172 / C++ https://www.acmicpc.net/problem/3172 3172번: 현주와 윤주의 재미있는 단어 게임 현주와 윤주는 일요일마다 재미있는 단어 게임을 하면서 시간을 보낸다. 단어 게임을 하던 중, 두 사람은 서로 좋아하지 않는 단어가 있다는 사실을 알게 되었다. 두 단어 A와 B가 있을 때, A가 B www.acmicpc.net [ 풀이 ] 문자열을 우선 정렬해놓자. 이제 정렬후 인덱스로만 보면 처음 문자열의 사전순을 알 수 있다. 이 인덱스를 문자열과 함께 묶어서 들고다니자. 이제 정렬한 문자열을 모두 뒤집는다. 뒤집고 다시 정렬한다. 이제 순회를 시작해보자. 순회의 방향은 항상 뒤집은 문자열이 앞서는 순으로 진행된다. 그럼 좋아하지 않는 순서쌍이 되려면 다음에 보는 문자열의 인덱스가 현재보는.. 2022. 8. 4. 백준 15678 / C++ https://www.acmicpc.net/problem/15678 15678번: 연세워터파크 첫 줄에 징검다리의 수 N과 문제에서 설명한 D가 주어진다. (2 ≤ N ≤ 105, 1 ≤ D ≤ N-1) 이어 N개의 정수로, 각 징검다리에 쓰인 수 Ki가 1번 징검다리부터 N번 징검다리까지 순서대로 주어진다. (-109 www.acmicpc.net [ 풀이 ] dp[j]=max(0, dp[k])+a[j] 이다. (단, k>=j-D , k qe || e > D; for (int i = 1; i > K[i]; ll ans = K[1]; upd(1, 1, n, 1, K[1]); for (int i = 2; i 2022. 8. 2. 백준 13555 / C++ https://www.acmicpc.net/problem/13555 13555번: 증가하는 부분 수열 길이가 N인 수열 A1, A2, ..., AN와 정수 K 주어진다. 이때, 수열 A의 부분 수열 중에서 길이가 K이면서 증가하는 부분 수열의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] naive하게 세워보자. dp[i][j]를 A1~Ai까지 길이 j인 증가 부분수열의 개수라고 하자. dp[i][j]=sum(dp[k][j-1])이 된다. (단, a[k] n >> k; for (int i = 1; i > a[i]; for (int i = 1; i 2022. 8. 2. 백준 12899 / C++ https://www.acmicpc.net/problem/12899 12899번: 데이터 구조 첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니 www.acmicpc.net [ 풀이 ] 값을 인덱스로, 그 값의 개수를 저장하는 세그트리를 만들어주자. (값을 인덱스로 세팅하는 방식은 자주 사용되는 방법이니 알아둡시다.) 중복에 주의하자. 이미 있는 수도 추가해줘야 X번째로 작은 수를 찾을 수 있다. 저장된 곳에서 X번째로 작은수는 값이 인덱스로 세팅된 세그트리에서 X번째 수를 찾으면 된다. [ Code ] #include using na.. 2022. 8. 1. 이전 1 2 3 4 다음