본문 바로가기

전체 글

 (136)
백준 온라인 저지 20951 유아와 곰두리차 문제 유아는 새해를 맞이하여 V.Nets의 자율 주행 자동차를 구매하였다. 유아는 새 차를 타고 바다로 가서 회를 잔뜩 먹고 올 것이다(유아는 감염병 예방을 위한 정부의 방역지침을 준수한다). 고속도로를 달리던 유아는 놀라 자빠질 수밖에 없었다. V.Nets의 자율 주행 시스템이 형편없었기 때문이다. V.Nets에 큰 배신감을 느낀 유아는 직접 자율 주행 자동차를 설계하기로 결심하였다. 곰두리차는 유아가 설계한 자율 주행 자동차이다. 곰두리차는 항상 인접한 정점 중 임의의 정점으로 이동한다. 유아는 출발점에서 도착점까지의 경로가 존재하고 시간이 무한하다면 곰두리차가 언제나 목적지에 도달할 수 있다고 믿고 있다. 유아는 문득 그래프가 주어졌을 때, 곰두리차가 지날 수 있는 경로가 몇 개인지 궁금해졌다. 하..
백준 온라인 저지 1025 제곱수 찾기 문제 지민이는 천장을 보다가 직사각형 격자판을 생각했고, 각 칸에 숫자를 한 자리씩 적어 놓았다. 수업시간이 너무 지루해서 지민이는 행의 숫자가 등차수열이고, 열의 숫자도 등차수열을 이루는 서로 다른 칸의 수열을 생각해 보았다. 그리고 나서 그 수열의 수를 모두 이어 붙였다. 이렇게 만든 수 중에 가장 큰 제곱수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 직사각형 격자판에 쓰여 있는 수가 주어진다. 모두 한자리이다. N과 M은 9보다 작거나 같은 자연수 또는 0이다. 출력 첫째 줄에 지민이가 만든 수 중에 가장 큰 제곱수를 출력한다. 만약 제곱수가 없다면 -1을 출력한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14..
백준 온라인 저지 17836 공주님을 구해라! 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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 #include #include using namespace std; struct pos { int row, col, time; }; int n, m, t; char map[100][101]; int moveY[] = {-1, 1, 0, 0}, moveX[] = {0, 0, -1, 1}; int bfs() { queue myQueue; myQueue.push(p..
백준 온라인 저지 12789 도키도키 간식드리미 문제 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두근 설레서 시험 공부에 집중을 못 한다. 이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다. 그런데 이게 무슨 날벼락인가! 그 곳에는 이미 모든 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었다. 설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다. 간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만에 번호표 순서로만 간식을 줄 수 있다고 말했다. 그제야 학생들이 순서대로 줄을 서려고 했지만 공간이..
백준 온라인 저지 1744 수 묶기 문제 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다. 예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다. 수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다. 수열이 주어졌을 때, 수열..
백준 온라인 저지 1992 쿼드트리 문제 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다 위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 ..
백준 온라인 저지 12849 본대 산책 문제 숭실 대학교 정보 과학관은 캠퍼스의 길 건너편으로 유배를 당했다. 그래서 컴퓨터 학부 학생들은 캠퍼스를 ‘본대’ 라고 부르고 정보 과학관을 ‘정보대’ 라고 부른다. 준영이 또한 컴퓨터 학부 소속 학생이라서 정보 과학관에 박혀있으며 항상 본대를 가고 싶어 한다. 어느 날 준영이는 본대를 산책하기로 결심하였다. 숭실 대학교 캠퍼스 지도는 아래와 같다. (편의 상 문제에서는 위 건물만 등장한다고 가정하자) 한 건물에서 바로 인접한 다른 건물로 이동 하는 데 1분이 걸린다. 준영이는 산책 도중에 한번도 길이나 건물에 멈춰서 머무르지 않는다. 준영이는 할 일이 많아서 딱 D분만 산책을 할 것이다. (산책을 시작 한 지 D분 일 때, 정보 과학관에 도착해야 한다.) 이때 가능한 경로의 경우의 수를 구해주자. ..
백준 온라인 저지 1440 타임머신 문제 다솜이는 타임머신을 타고 8364년으로 갔다. 다행히 지구는 평화롭다. 다솜이는 2008년으로 돌아가기 전에 시계를 샀다. 다솜이는 시계를 볼 줄 모르기 때문에, 디지털 시계를 샀다. 디지털 시계는 HH:MM:SS와 같은 모양으로 시간을 나타내 준다. 그리고 앞에서부터 차례대로 HH는 시, MM은 분, SS는 초를 나타낸다. 다솜이는 8364년에는 2008년과 같은 방법으로 시간을 나타내는지 모른다. 2008년엔 시:분:초를 나타내는지만, 8364년엔 분:시:초로 나타낼지도 모른다. 다행히 시는 01부터 12, 분은 00부터 59, 초는 00부터 59를 나타낸다. 다솜이의 시계에 쓰여 있는 숫자가 주어졌을 때, 이 시간을 읽을 수 있는 가능한 방법의 수를 출력하는 프로그램을 작성하시오. 나타내는 시..

티스토리툴바