2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net (이 문제 풀다가 추억 돋아서 BEMANI REMIX 듣다가 살짝 해 멘 문제) DP는 DP인데 재귀를 사용하는 DP입니다. 처음에는 왼발 오른발 위치를 기억하고 i번째 일을 마쳤을 때 값을 기준으로 점화식을 놓으려다가 막혀서 재귀 함수를 돌리되 memozation을 이용하는 것으로 풀었습니다. 가능한 case의 수는 지시사항이 N개 있을 때 2^N개입니다. 이를 다 처리하려면 답이 없습니다. 일단 처음 지시사항을 실시할 때 왼..
colab에 많은 패키지들이 기본적으로 내장되어있지만 없는 라이브러리나 예전 버전인 것들이 많습니다. 예를 들어 colab에는 googlemaps가 설치 안 돼있어서 !pip install googlemaps 이런 식으로 매번 설치해야 합니다. https://stackoverflow.com/questions/55253498/how-do-i-install-a-library-permanently-in-colab How do I install a library permanently in Colab? In Google Colaboratory, I can install a new library using !pip install package-name. But when I open the notebook again..
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/1739 1739번: 도로 정비하기 첫째 줄에 테스트 데이터의 개수 T(1≤T≤10)가 주어진다. 각 테스트 데이터의 첫째 줄에는 세 정수 N, M, K가 주어진다. 다음 K개의 줄에는 각 버스의 운행 정보를 나타내는 네 정수 A, B, C, D가 주어 www.acmicpc.net 한창 그래프 이론, 특히 2-SAT을 풀던 시절 난이도에 쫄지 않고 도전해서 생각보다 빠른 시간내 해결했던 문제입니다. 문제 조건을 보면 시장이 도로들에 방향성을 주어서 일방통행을 시키겠다고 합니다. 이말인 즉슨 (1) 도로는 (위, 아래) 또는 (왼쪽, 오른쪽)으로만 값을 가질 수 있음을 알 수 있고 도로의 혼잡을 줄이기 위하여 최대 2개의 도로만 이용하므로 (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