문제 링크 https://www.acmicpc.net/problem/1327 1327번: 소트 게임 홍준이는 소트 게임을 하려고 한다. 소트 게임은 1부터 N까지 정수로 이루어진 N자리의 순열을 이용한다. 이 게임에선 K가 주어진다. 어떤 수를 뒤집으면, 그 수부터 오른쪽으로 K개의 수를 뒤집 www.acmicpc.net ◆문제 해결 및 설명◆ 문제 해설 : 순열을 일정길이만큼만 뒤집을 수 있을 때, 최소 몇 번 만에 오름차순으로 만들 수 있는가 우선 순열이 최대 8의 길이를 가지기 때문에 브루트포스를 통해서 풀 수 있겠다는 생각이 들었다. 순열을 뒤집어야 하는데, string의 reverse()를 사용하면 편하여 string으로 input을 받아주었다. 알고리즘은 BFS로 구현을 하였으며, 모든 순열을..
문제 링크 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net ◆문제 해결 및 설명◆ 문제 해설 : 1에서 출발해 두 개의 정점을 지나 N에 도달하는 최단 경로의 길이를 출력한다. 길찾기 골드4의 문제... 다익스트라다! 다익스트라는 알고 있으리라고 생각하고 설명을 해드리겠다. 우선 일반적인 다익스트라와 다른 점이라면 마지막으로 입력해준 두 개의 정점을 지나야 한다는 것이다. 이것들을 b, c라고 하고 ..
문제 링크 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net ◆문제 해결 및 설명◆ 문제 해설 : 문자열을 커서에 따른 Command로 수정한 결과물을 출력하여라! 처음에 문제조건이 0.3초 인걸 봤지만 string으로 짜보았다.(글 하단에 첨부) 바로 시간초과! 알고리즘을 다시 보니 문자열을 삽입과 삭제할 때 걸리는 시간이 가장 길다고 판단되어서 이 부분을 substr로 복사붙여넣기? 로 줄일 수 있나 다시 코드를 짜고 제출했으나 시간초과! 가 ..
