문제 링크 https://www.acmicpc.net/problem/16720 가장 왼쪽 위에서 출발해 오른쪽 밑으로 도착해야한다. 맨 윗줄과 아랫줄 사이에는 벽들이 있는데, 한 줄당 세 칸의 벽과 한 칸의 통로가 있으며, 한 줄을 통째로 밀어 통로의 위치를 이동시킬 수 있다. 간단하게 풀 수 있다. 우선 현재 위치에서 왼쪽 혹은 위로 가는 경로는 당연히 제외한다. 저 두 상황을 제외한다면 단순히 인접한 길로 이동하는 총 시간은 어떻게 가도 같게된다. 다음으로 어떤 벽을 어떻게 회전시킬지를 결정해야 한다. 통로의 위치를 한 열로 몰아준다.생각하기 싫어서 1, 2, 3, 4번 열 모두 한 번씩 해본 뒤 가장 작은 값을 구했다. 답을 { 3 (오른쪽으로 이동) + (n - 1) (아래로 이동) + $\sum..
문제링크https://www.acmicpc.net/problem/16719 문자열을 하나씩 추가해나갈 때, 그 문자열들이 사전 순으로 출력되게끔 해야 한다. 어떤 구간에서 가장 작은 문자를 찾아 체크하고, 전체 문자열에서 체크된 문자들만 출력한다. 그다음 그 문자를 기준으로 오른쪽 구간, 왼쪽 구간의 순서로 처리한다. 예제의 STARTLINK로 예를 들자. 1) 우선 전체 구간 중 가장 작은 문자는 A이다. A에 체크 후 출력한다. 문자 S T A R T L I N K 인덱스 0 1 2 3 4 5 6 7 8 출력 O 2) A를 기준으로 오른쪽구간 [3, 8]에서 같은 과정을 거친다.가장 작은 문자 I에 체크 후 체킹된 문자들을 출력한다. 문자STARTLINK인덱스012345678출력 O O 3) I 기준..
0. 들어가기 전에 첫 알고리즘 포스트입니다. 이번에 쓸 내용은 CCW입니다. 원래는 기하 알고리즘들을 전반적으로 다루려고 했는데 생각보다 글이 길어져서 CCW만 쓰게 되었습니다. 본 글의 내용은 고등학교 과정(2007 개정 교육과정 기준)인 '기하와 벡터' 수준의 지식만 있으면 얼추 알아들을 수 있지만, 혹시 그렇지 않다면 설명을 봐도 이해가 안가실 수 있습니다. 급하게 CCW를 사용해야 한다면 바로 아래의 한 줄 요약과 본문 하단의 코드(여기)만 보고 쓰시면 됩니다. 1. CCW 기하 알고리즘을 공부하기 전에 필수로 알아야 할 것이 있는데, 그게 바로 CCW입니다. 거의 사칙연산처럼 쓰게 될 거에요. CCW는 Counter Clockwise의 약자로써, 평면 위에 놓여진 세 점의 방향관계를 구할 수 ..
문제 링크 15922 아우으 우아으이야!! 문제와 같은 문제입니다. 예전에 썼던 풀이 그대로 퍼올게여. 문제를 풀기 위해 수직선들을 좌표가 낮은 순으로 정렬하자. 그리고 앞의 수직선부터 탐색한다. 인접한 두 수직선의 관계는 다음과 같다. 빨간 선의 양 끝점을 $s, e$라 하고, 파란 선의 양 끝점을 $ns, ne$라 하자. ①은 $s \leq ns$ & $ne \leq e$인 경우이고, 더 작은 선분을 무시하는걸로 해결할 수 있다. ②는 $ns < e$인 경우이고, 중복해서 더해지는 $e - ns$값을 빼주면 된다. ③의 경우엔 그냥 둘 다 더하면 된다. 파란 선은 현재 내가 보고있는 선분, 빨간 선이 파란 선분의 바로 직전 선분이다. 정답 코드
문제 링크 기억하는 알파벳이 판별할 문자열에 순서대로 들어있는지 확인하면 된다. 비슷한 문제로 15904 UCPC는 무엇의 약자일까? 가 있다. 기억하는 알파벳의 문자열을 $s$라 하고 판별해야 하는 문자열을 $x$라 하자.$s$는 별개의 인덱스 $idx$를 가지고, $x$를 순서대로 탐색하면서 $s[idx] = x[i]$이면 $idx$를 증가시킨다.$idx$가 $s$의 끝까지 간다면 모두 나온 것이니 "true"를 출력하고, 그렇지 않으면 "false"를 출력한다. 정답 코드 질문 및 피드백 환영합니다.