2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 아이디어 숫자들을 정점으로 생각하면 뽑은 숫자들의 집합이 일치한다 => 사이클이 있다고 볼 수 있다. 사이클을 검출하는 방법 : DFS DFS를 돌다가 DFS가 아직 다 돌지않은 정점을 만나게 되면 사이클이 있다고 생각할 수 있다. (다만 방문여부와는 별개로 생각해줘야한다. 처음 방문하는 정점도 DFS를 다 돌진 않은 상태니까) DFS를 돌면서 자신이 이전에 방문한 정점을 저장해준다면 DFS가 다 안돈 정점부터 차례대로 자기 자신을 만날 때 까지 정..
https://www.acmicpc.net/problem/1562 생각보다 엉뚱한 곳에서 해멘 문제입니다. 계단수는 문제 조건처럼 45656마냥 인접한 각 자리 숫자들이 1씩 차이나는 숫자입니다. 몰랐는데 이 문제가 쉬운 문제로 N이 주어졌을 때 마지막 자리숫자를 저장해서 푸는 문제가 있었죠. 이 방식이 원본 문제에서는 적용이 안될줄 알고 규칙을 찾아 점화식으로 풀려했는데 네, 원본 문제에서도 적용됩니다. dp배열을 다만 3차원으로 써서 dp[현재 수의 길이][마지막 자리의 숫자][현재 상태] = 숫자의 개수 이런 식으로 저장하는데 이때 현재 상태는 비트 마스킹을 활용하여 모든 숫자가 한번 씩 사용됬는지 표시합니다. 예를 들어 0 0 0 0 0 0 0 1 0 0 이면 숫자 2를 제외하고는 나머지 숫자가 ..
https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 전형적인 그래프 이론과 dp가 섞인 문제입니다. 파이프의 머리를 기준으로 위치를 잡아주면 (1,2)에서부터 (n,n)까지 이동하면 되는데 이때 파이프의 자세를 고려해줘야 합니다. 파이프가 가로로 누워있다면 45도밖에 못 움직이기에 가로로 평행이동하거나 대각선 아래로 이동하면서 오른쪽 아래 대각선이 될 것입니다. 이와 마찬가지로 세로인 경우도 제한 사항이 생기며 대각선인 경..
- Total
- Today
- Yesterday