티스토리 뷰
1294번: 문자열 장식
첫째 줄에 단어의 개수 N이 주어진다. N은 최대 20이다. 둘째 줄부터 N개의 줄에 단어가 주어진다. 단어는 최대 1,000글자이고, 공백은 없이 알파벳 대문자로만 구성되어 있다.
www.acmicpc.net
첨엔 포인터를 써야하나 생각했지만 그냥 벡터에 문자열 담아놓고 쓴 글자를 지우는 방식을 사용하기로 했다.
v[j].erase(v[j].begin());erase라니,, 이게 C++?
또 substr 메소드로 첫 글자가 같을때 추가 비교를 해주었고, 느릴것 같았으나 128ms로 가뿐히 통과했다. 맞힌 사람 들어가보니 0ms도 있던데 이건 어떻게 한거지..
질문 들어가서 좀 읽어보니까 pq써서 하면 편하고 빠르게 할 수 있을지도? 매번 substr 따는거보다 비교연산자 정의해서 바로바로 검사해서 정리해놓는 식으로 하면 빠르게 할 수 있을것 같다.
아래 문제들은 순열 사이클 분할을 사용하는 그리디 문제들이다. 수열을 정렬할 때 두개의 자리를 바꾸는 형식으로 진행하고, 바꿀 때 마다 특정 비용이 드는 상황에서 이를 그래프로 해석해 사이클을 찾아 사이클 내에서 최소 비용을 내는 인자를 사용해서 사이클을 모두 정렬한다. 이 형식을 모든 사이클에 대해서 하면 최소 비용으로 수열을 정렬할 수 있다.
2569번: 짐정리
첫째 줄에 짐칸의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 짐의 무게가 차례대로 주어진다. 짐칸의 수는 1,000이하의 자연수이며, 짐의 무게는 10,000이하의 자연수이다. 모든 짐의 무게는
www.acmicpc.net
두개의 자리를 바꿀 때 드는 비용이 두개의 무게의 합인 경우이다. index랑 값을 { value, i }로 같이 저장해놓고, 값을 기준으로 정렬을 시키고 chk배열을 사용해서 사이클을 탐색한다. 사이클의 길이가 1인 경우(이미 제자리에 있는 경우, i == 현재 index)는 미리 chk배열에서 true를 넣어 놔서 배제하거나 cnt변수로 사이클의 길이를 세서 cnt == 1인 경우 더한만큼을 다시 빼주는 형태(ans -= v[i].value)로 구현해도 된다. 빼먹기 좋은 아이디어는 사이클을 빠져나온 후 한번 더 확인을 해주어야 하는데 사이클 내부의 최솟값으로 돌리는게 아니고 전체의 최솟값을 사이클 최솟값과 바꿔서 돌리는 경우가 최소일 수 있다. 따라서 사이클을 빠져나오고 후자를 계산한 뒤 둘중 작은 값을 저장하고, 마지막에 각 사이클별 비용을 더하는 방식으로 구현했다.
2322번: 아령
첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 걸려 있는 순서대로 아령의 무게가 주어진다. 각 아령의 무게는 230보다 작거나 같은 자연수이며 답이 231-1보다 작거나 같게 되도록 주어진
www.acmicpc.net
거의 동한데 같은 코드로는 AC를 못받는다. 이유는 범위. 각 무게가 int의 최대값이어서 long long을 사용해주어야 되고, N이 10만이기 때문에 그 이상으로 넘어갈 걱정은 안해도 된다.
원래 아령이랑 똑같은게 두개나 더 있었는데 다 짤렸다;;
'코딩일지' 카테고리의 다른 글
| 9월 일지 (0) | 2023.09.30 |
|---|---|
| 백준 그리디 일지 (3) (0) | 2023.04.29 |
| 백준 DP 일지 2 (0) | 2023.04.20 |
| 백준 그리디 일지 (1) (1) | 2023.03.31 |
| 백준 DP 일지 (1) (0) | 2023.03.29 |