본문 바로가기

Problem Solving83

[Python]15559. 내 선물을 받아줘 https://www.acmicpc.net/problem/15559 15559번: 내 선물을 받아줘 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000, 1 < N×M ≤ 1,000,000) 둘째 줄부터 N개의 줄에는 구사과가 있는 곳의 지도가 주어진다. 지도에 쓰여 있는대로 이동했을 때, 지도를 벗어나는 경우는 없다. www.acmicpc.net 12345678910111213141516171819202122232425n, m = map(int, input().split())MAP = [list(input()) for _ in range(n)]check = [[0]*m for _ in range(n)]dic = {'N':(-1,0), 'S':(1,0), 'E':.. 2019. 4. 14.
[Python]13335. 트럭 https://www.acmicpc.net/problem/13335 13335번: 트럭 문제 강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최 www.acmicpc.net 친애하는 친구가 아이디어를 줬다! 현재시간에서 다리에 들어갈 때 시간을 빼라는 것! 그 생각을 못하고 다리에 머무르는 시간을 계속 카운트.. 2019. 4. 13.
[Python]16985. Maaaaaaaaaaze https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 의미한다. www.acmicpc.net Step1. 순열 생성 -> 블록이 쌓이는 순서를 생성해준다. 여기서는 5! 경우의 수 Step2. 회전 -> 각 층에 있는 블록은 독립적으로 회전한다. 블록당 4번 회전할 수 있으므로, 4^5 의 경우의 수 Step3. 탐색 -> (0,0,0) 부터 (4,4,4) 까지 BFS탐색으로 최단거리를 리턴한다. 최악일때 5*5*5 3차원 큐브에 있는 1칸짜리 블록은 상하.. 2019. 4. 12.
[Python]17070. 파이프 옮기기1 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 www.acmicpc.net 처음엔 DFS형태로 check배열 생성한다음 모든 경로를 다 탐색했으나.. 계속 60% 쯤에서 계속 시간초과가 발생했다. 다.. 2019. 4. 12.
[Python]16918. 봄버맨 https://www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 비교적 간단한 시뮬레이션 문제 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 direction = ((-1, 0), (1, 0), (0, -1), (0, 1)) r, c, n = map(int, input().split()) MAP = [list(input()) for _ i.. 2019. 4. 11.
[Python]5373. 큐빙 https://www.acmicpc.net/problem/5373 5373번: 큐빙 문제 루빅스 큐브는 삼차원 퍼즐이다. 보통 루빅스 큐브는 3×3×3개의 작은 정육면체로 이루어져 있다. 퍼즐을 풀려면 각 면에 있는 아홉 개의 작은 정육면체의 색이 동일해야 한다. 큐브는 각 면을 양방향으로 90도 만큼 돌릴 수 있도록 만들어져 있다. 회전이 마친 이후에는, 다른 면을 돌릴 수 있다. 이렇게 큐브의 서로 다른 면을 돌리다 보면, 색을 섞을 수 있다. 이 문제에서는 루빅스 큐브가 모두 풀린 상태에서 시작한다. 윗 면은 흰색, 아랫 면은 노란 www.acmicpc.net 큐빙 문제를 풀기전에 아래 문제를 먼저 풀어보자. https://br-brg.tistory.com/25 또한 큐빙 문제를 디버깅하는 동안 아.. 2019. 4. 11.
[Python]16939. 2x2x2 큐브 https://www.acmicpc.net/problem/16939 16939번: 2×2×2 큐브 첫째 줄에 2×2×2 루빅스 큐브 각 면의 각 칸 색상이 주어진다. 색상은 1부터 6까지의 자연수로 나타내며, 각 자연수는 총 4번 등장한다. i번째 수가 의미하는 칸은 아래와 같다. www.acmicpc.net 5373. 큐빙을 풀기전에 미리 풀어보면 좋은 문제이다. 여기서 pitch, yaw, roll 은 3차원 축에 대한 회전방향을 나타내는 용어이다. 또한 큐브의 경우 한방향으로 3번 회전하는 것은 곳 1번 반대방향으로 회전한 것과 같다. 따라서 코드는 다음과 같다. ccw는 반시계방향, cw는 시계방향이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2.. 2019. 4. 10.
[Python]16235. 나무 재테크 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다. 상도는 전자통신공학과 출신답게 땅의 양분을 조사하는 로봇 S2D2를 만들었다. S2D2는 1×1 크기의 칸에 들어있는 양분을 조사해 상도에게 전송하고, 모든 www.acmicpc.net 이 문제는 시뮬레이션 문제로 문제를 분석해서 코드를 짜는데 크게 어렵진 않았다. 다만 나무를 1차원 리스트로 통째로 관리해서 푼다면.. 2019. 4. 10.
[Python]16236. 아기 상어 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크 www.acmicpc.net BFS + 약간의 시뮬레이션 문제라고 생각한다. 누구는 BFS만으로도 푼다. 코드구현은 한시간 걸린듯 한데 디버깅이 너무너무너무 오.. 2019. 4. 9.
728x90
반응형