본문 바로가기

전체 글

 (73)
백준 13913번: 숨바꼭질 4 백준 13913: 숨바꼭질 4 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 www.acmicpc.net 예전에 풀었던 숨바꼭질 시리즈인데 오랜만에 풀어서 그런지 시간초과로 한번에 풀지를 못했다. 결국 예전 코드를 참조해서 다시 기억을 되살려서 풀어냈다. DFS를 사용하면..
백준 11967번: 불켜기 백준 11967: 불켜기 11967번: 불켜기 문제 농부 존은 최근에 N*N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2≤N≤100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다. 베시는 유일하게 불이 켜져있는 방인 (1,1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으 www.acmicpc.net BFS로 푸는 문제인데 푸는 방법이 조금 귀찮았던 문제이다. 방문 체크 여부는 두개의 배열을 사용했다. 방 하나에는 스위치가 여러개 있을 수가 있어서 방 하나가 가지고있는 스위치..
백준 1600: 말이 되고픈 원숭이 백준 1600: 말이 되고픈 원숭이 1600번: 말이 되고픈 원숭이 첫째 줄에 자연수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있는 곳으로는 이동할 수 없다. 시작점과 도착점은 항상 평지이다. W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다. www.acmicpc.net 제한시간 : 2초 메모리 : 256MB 처음엔 DP 문제인줄 알고 DFS를 이용해서 풀려했지만 풀리지 않았고 BFS로도 잘 풀리지 않았다. 결국에는 구글링으로 해결했다. 문제를 처음봤을 때 K의 갯수가 제한이 필요한가 의문이 들었었는데 구글링이 결국 답을 알려주었고, BF..
백준 3197번: 백조의 호수 백준 3197번 백조의 호수 3197번: 백조의 호수 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세 가지 예가 있다. ...XXXXXX..XX.XXX ....XXXX.......XX www.acmicpc.net 시뮬레이션 느낌이 나는 BFS 문제이다. 문제의 답을 내는대에는 많이 어렵지는 않지만 시간 제버 부분이 많이 촉박하다. 덕분에 시간초과로 꽤 애를 먹었다. BFS를 쓸 때..
백준 15656번: N과 M (7) 백준 15656번: N과 M (7) 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. www.acmicpc.net 재귀를 이용해서 풀 수 있는 간단한 문제이다. 배열을 입력하고 문제에 맞게 배열 조합들을 출력하면 된다. 문제 조건 중 수열이 사전 순으로 증가해야하기 때문에 정렬을 해야했다. 1. 입력한 배열을 오름차순으로 정렬 2. 중복 허용 가능이어서 다른 조건 필요없이 배열 인덱스가 0번째부터 N-1까지 M번 돌 수 있게 작성했다. 3. M까지 재귀로 배열의 숫자 하나하나를 벡터에 넣는다. 4...
백준 14499번: 주사위 굴리기 백준 14499번: 주사위 굴리기 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 주사위를 놓은 칸에 쓰여 있는 수는 항상 0이다. 지도의 각 칸에 쓰여 있는 수는 10을 넘지 않는 자연수 또는 0이다. 마 www.acmicpc.net 주사위를 지도위에 굴려서 이동할때마다 주사위의 윗면 값을 출력하는 문제이다. 난이도는 어렵지 않은데 x, y좌표 값이 row, col이 내 생각과는 반대로 되어있..
백준 5014번: 스타트 링크 백준 5014번: 스타트 링크 DFS로 풀려하다가 DP도 사용해서 풀었다. 어렵게 풀지는 않았다. 현재 위치에서 스사트링크 위치까지 이동하는데 지정된 층수만큼 up하거나 down할 수 밖에 없다. 만약 엘레베이터로 갈 수 없다면 계단을 이용하라는 문구를 띄운다. 내가 생각한 조건은 다음과 같다. 1. up과 down을 했을 때 0층 초과 F층 이하 범위에서 엘레베이터가 움직이여야 한다. 2. up과 down으로 해당 층으로 이동가능 해야한다. 3. 이동하는 방법이 여러개 있을 때 먼저 도달하는 값이 최소값이다. 코드는 다음과 같이 작성했다. 이동했을 때 그 층이 이동 횟수의 최소값을 가지고 있어야하니까 dp는 모두 최고값인 1000001로 초기화를 했다. 시작층의 위치의 dp 값은 0으로 시작하여 up과..
백준 6593번: 상범 빌딩 백준 6593번: 상범 빌딩 6593번: 상범 빌딩 문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서 www.acmicpc.net 1트! BFS로 풀수 있는 간단한 문제였다. 3차원이기 때문에 인덱스 위치만 헷갈리지 않으면 되는 것 같다. 동서남북상하로 이동할 때 벽('#')으로만 이동하지 않게하고 출..

티스토리툴바