본문 바로가기

그리디

백준 1071번 소트 http://icpc.me/1071 1071번: 소트 N개의 정수가 주어지면, 이것을 연속된 두 수가 연속된 값이 아니게 정렬(A[i] + 1 ≠ A[i+1])하는 프로그램을 작성하시오. 가능한 것이 여러 가지라면 사전순으로 가장 앞서는 것을 출력한다. www.acmicpc.net 풀이 간단한 그리디 문제입니다. 사전순으로 앞선 배열을 만들어야 하기 때문에 앞에서 최대한 작은 수를 사용해야 합니다. 앞서 $i$개의 수를 최적으로 출력했다고 가정할 때 가능하다면 무조건 출력하지 않은 수 중 최솟값을 출력해야 하며, 최솟값을 출력할 수 없다면 두 번째로 작은 값을 출력해야 합니다. 최솟값을 출력할 수 없는 경우는 두 가지입니다. 1) $i$번째로 출력한 수 + 1 == 최솟값일 때 2) 출력하지 않은 수에서.. 더보기
백준 20442번 ㅋㅋ루ㅋㅋ http://icpc.me/20442 20442번: ㅋㅋ루ㅋㅋ 어떤 문자열에서 몇 개의 문자를 지워서 부분 수열을 만들 수 있다. 예를 들어, ABC의 부분 수열은 ABC, AB, BC, AC, A, B, C와 빈 문자열이다. www.acmicpc.net 풀이 투 포인터를 이용하여 풀었습니다. 왼쪽에서 $i$번째 R을 기준으로 왼쪽에 있는 K의 수를 $lk[i]$, 오른쪽에 있는 K의 수를 $rk[i]$라고 하겠습니다. 이때 $l$번째 R부터 $r$번째 R까지 사용한 ㅋㅋ루ㅋㅋ문자열의 최대 길이는 $r - l + 1 + 2\times min(lk[l], rk[r])$이 됩니다. R은 $r - l + 1$개, K는 왼쪽 오른쪽 각각 $min(lk[l], rk[r])$개씩 사용할 수 있기 때문입니다. 단순히.. 더보기
Codeforces Raif Round 1 (Div. 1 + Div. 2) A~C번 풀이 중간고사가 4일 남았는데 참가했습니다. 대회 중 A~C번을 풀었습니다. 중간고사ㅠㅠㅠㅠㅠ A번 - Box is Pull 문제 Problem - A - Codeforces codeforces.com 문제 설명 $(x_1, y_1)$의 박스를 $(x_2, y_2)$로 끌고 가려 합니다. 박스와 인접해 있을 때 박스를 끌면 박스는 내가 있던 위치로 이동하고, 나는 박스 반대편으로 한 칸 이동합니다. 박스를 끌지 않고도 한 번에 한 칸씩 움직일 수 있으며, 내 처음 위치는 마음대로 정할 수 있습니다. 이때 박스를 $(x_1, y_1)$에서 $(x_2, y_2)$로 옮기기 위해 필요한 최소 이동 횟수를 구하는 문제입니다. 풀이 만약 출발지와 목적지의 x좌표가 같다면 y좌표의 차이가 이동 횟수가 됩니다. 마찬가지로.. 더보기

티스토리툴바