tony9402

1347번: 미로 만들기 홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍 www.acmicpc.net 이 문제는 주어진 문자열 순으로 구현을 하면 되는 문제이다. 주어지는 문자열의 최대 길이는 50으로 101x101 크기의 배열을 만들어 (50, 50)에서 출발하여 주어진 문자열 대로 이동하고 방문한 점을 .으로 방문하지 않은 점을 #으로 출력하면 된다. 미로를 출력하는 범위는 .을 포함하는 가장 작은 직사각형의 크기 및 위치를 관리하면 된다. import sys def input(): return sys.stdin.readline().rstrip() N = ..

[문제] 백준 3025 돌 던지기 [알고리즘] 시뮬레이션 [시간복잡도] $ O(N + R) $ [솔루션] 일단 딱봐도 시뮬레이션을 해야한다. 하지만 단순 시뮬레이션으로 소스코드를 짠다면 $ O(NR) $로 무조건 시간초과이다. 이를 어떻게 줄일지 아이디어를 생각해봐야한다. 아이디어 1 : 돌 던졌을때 직선으로 내려가는 부분을 잘 정리하면 시간초과가 해결될 것 같다. 결론부터 말하자면 이것도 시간초과이다. 벽의 분포로 인해 돌이 지그재그로 떨어지는 경우 돌 던지는 경우마다 $ O(R) $을 갱신하기 때문에 TLE이다. 아이디어 2 : 그렇다면 지그재그로 가는 경로도 잘 정리하면 될 것 같다. 이거 또한 $O(R)$의 시간복잡도를 가질 것이다. 따라서 시간초과. 아이디어 3 그렇다면 어떻게 짜야할까? 바로,..

문제링크 : 바로가기 16939번: 2×2×2 큐브 첫째 줄에 2×2×2 루빅스 큐브 각 면의 각 칸 색상이 주어진다. 색상은 1부터 6까지의 자연수로 나타내며, 각 자연수는 총 4번 등장한다. i번째 수가 의미하는 칸은 아래와 같다. www.acmicpc.net 큐브를 한 번만 돌려서 모든 면을 맞출 수 있는지 확인하는 문제이다. 배열 돌리는 연산을 구현하는 것이 살짝 까다롭다. 큐브는 3차원이기 때문에 돌리는 방향은 3가지로 표현 할 수 있다. 전개도를 고정하고 돌릴 수 있는 방향을 써보면 위, 아래( == 위 x3 == -위), 왼쪽, 오른쪽( == 왼쪽 x3 == -왼쪽), 시계방향, 반시계방향(== 시계방향 x3 == -시계방향)이다. 1. 위쪽 방향 2. 왼쪽 방향 3. 반시계 방향 1번에서 ..