개발노동자

문제 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다. 농부 현서에게는 지도가 있습니다. N개의 헛간과, 소들의 길인 M개의 양방향 길이 그려져 있고, 각각의 길은 C마리의 소들이 있습니다. 소들의 깉은 두 개의 떨어진 헛간인 A와 B를 잇습니다. 두 개의 헛간은 하나 이상의 길로 연결되어 있을 수도 있습니다. 농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다. [2]--- / | \ /1 | \ 6 / | \ [1] 0| --[3] \ | / \2 4\ | /4 [6] \ | / /1 [4]-----[5] 3..

문제 매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D 킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커므가 많아서 정말 운전하기도 힘들다. 어느 날 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행 할 수는 없다. 5 150 0 50 10 0 50 20 50 100 10 100 151 10 110 140 90 틀린 점 - 처음에 dist 배열에 크기가 정말 고민이었는데 문제에서 10000을 넘기지 않는다 하여 10000을 주고 풀어봤는데 그러기에는 인접리스트 크기도 같게 줘야했기에 이렇게 가다가 분명 메모리 초과 또는 시간 초과로 틀릴 거 같아 계속 시도하다가 답을 봐버렸다.... 풀이 dist 배열을 10001의 크기에 모두..

문제 2개의 문자열 s와 t가 주어졌을 때 s가 t의 부분 문자열인지 판단하는 프로그램을 작성하라. 부분 문자열을 가지고 있는지 판단하는 방법은 t에서 몇 개의 문자를 제거하고 이를 순서를 바꾸지 않고 합쳤을 경우 s가 되는 경우를 이야기한다. sequence subsequence person compression VERDI vivaVittorioEmanueleReDiItalia caseDoesMatter CaseDoesMatter 풀이 - 입력 크기를 안 준 문제는 처음 풀어봤는데 신선하다. 처음에는 자료구조를 사용해서 contains로 접근했는데 그러면 순서가 상관 없어도 true가 나와버려서 그냥 주어진 값을 바로 charAt으로 대조하면서 맞으면 다음 값을 조회하는 식으로 변경했다. 그리고 그렇게..

문제 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다. 예를 들어 K=4,K=2,K=1 일 떄 다음과 같이 그래프가 구성되어 있다고 가정하자 이 떄 1번 도시에서 출발하여 도달할 수 있는 도시 중에서 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다. 풀이 - 방향성 그래프, 거리를 구한다 --> 다익스트라 - 출발점부터 시작하여 dist 배열에다가 1씩 추가하면 된다. - 그..

문제 다솜이는 사람의 마음을 읽을 수 있는 기계를 가지고 있다. 다솜이는 이 기계를 이용해서 2008년 4월 9일 국회의원 선거를 조작하려고 한다. 다솜이의 기계는 각 사람들이 누구를 찍을 지 미리 읽을 수 있다. 어떤 사람이 누구를 찍을 지 정했으면, 반드시 선거 때 그 사람을 찍는다. 현재 형택구에 나온 국회의원 후보는 N명이다. 다솜이는 이 기계를 이용해서 그 마을의 주민 M명의 마음을 모두 읽었다. 다솜이는 기호 1번이다. 다솜이는 사람들의 마음을 읽어서 자신을 찍지 않으려는 사람을 돈으로 매수해서 국회의원에 당선이 되게 하려고 한다. 다른 모든 사람의 듣표수 보다 많은 득표수를 가질 때, 그 사람이 국회의원에 당선된다. 3 5 7 7 이번 문제에서 주어진 예제가 다 통과하는데 계속 9퍼에서 틀리..

문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추 흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다. 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어놓았다. 배추들이 모여잇는 곳에는 배추 흰 지렁이가 한 마리만 있으면 되므로 서로 인접해 있는 배추들이 ..

문제 알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1 크기의 방으로 이루어져있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다. 알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 사하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x,y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동할 수는 업삳. 벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으..

문제 수빈이는 동생과 숨바꼭질을 하고있다. 수빈이는 현재 점 N에 있고, 동생은 점 K에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빨느 시간이 몇 초 후인지 구하는 프로그램을 작성하시오 디버깅을 통한 풀이 첫 시작은 Node(수빈의 위치, 시간은 0) 으로 먼저 queue에 담는다. 첫 if문은 수빈이가 현재 있는 위치가 동생의 위치와 같은 경우 작은 값을 넣는 것인데 이떄 처음 들어가는 값이 바로 min변수에 값이 할당되어야 하므로 min은 Integer.MAX_VALU..

문제 nxn 바둑판 모양으로 총 n제곱개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 서로 붙어 있는 두 개의 흐니 방 사이에는 문이 있어서 지나다닐 수 있다. 우니줄 맨 왼쪽 방은 시작방으로서 항상 흰방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다. 시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데 아래 그림의 경우에는 시작 방에서 끝방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다. 아래 그림은 n=8인 경우의 한 예이다. 위 그림에서는 두 개의 검은방(예를 들어 (4,4의 방과 (7,8)의 방) 을 흰 방으로 바꾸면 , 시작 방에서 끝방으로 ..

문제 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어의 점수는 레벨을 클리어하면서 얻은 점수의 합으로, 이 점수를 바탕으로 온라인 순위를 매긴다. 동준이는 레벨을 난이도 순으로 배치했다. 하지만, 실수로 쉬운 레벨이 어려운 레벨보다 점수를 많이 받는 경우를 만들었다. 이 문제를 해결하기 위해 동준이는 특정 레벨의 점수를 감소시키려고 한다. 이렇게해서 각 레벨을 클리어할 때 주는 점수가 증가하게 만들려고 한다. 각 레벨을 클리어할 때 얻는 점수가 주어졌을 때, 몇 번 감소시키면 되는지 구하는 프로그램을 작성하시오. 점수는 항상 양수이어야 하고, 1 만큼 감소시키는 것이..