문제 링크: https://www.acmicpc.net/problem/30464 문제건덕이는 학교에 가기 너무 싫은 나머지 최대한 늦게 학교에 도착하려고 한다. 등굣길은 N개의 칸이 가로로 놓인 형태이며, 각 칸은 가장 왼쪽 칸부터 오른쪽으로 1부터 N까지 번호가 매겨진다. 건덕이는 1번 칸에, 학교는 N번 칸에 존재한다.건덕이는 처음에 학교를 바라보는 방향으로 서 있다. 등교하는 방법은 특이한데, 1분마다 현재 자신이 서 있는 칸에 쓰인 수만큼 바라보는 방향으로 이동한다. 이때, 등굣길을 벗어나도록 이동할 수 없다.건덕이는 바라보는 방향을 최대 두 번 반전할 수 있다. 학교가 있는 칸에 처음으로 도착하는 시간을 최대한 늦추면 출발 몇 분 뒤에 도착할까? 건덕이가 방향을 반전하는 데 드는 시간은 무시한..
문제 링크: https://www.acmicpc.net/problem/31804 문제자료구조 시험에서 우찬이는 a점을 받았고, 상훈이는 우찬이보다 높은 b점을 받았다. 우찬이는 상훈이보다 점수가 낮아서 화가 났지만, 공부를 하나도 하지 않아서 상훈이보다 시험을 잘 볼 수는 없다는 것을 알고 있었다. 하지만 우찬이는 최소한 동점을 받고 싶었기 때문에, 자신의 수를 바꾸는 마법을 배워서 다음 3가지 마법을 사용할 수 있게 되었다.물 주기: 수에 물을 주면 수가 1 커진다.밥 주기: 수에 밥을 주면 수가 2배가 된다.chance!: 수에 chance!를 외치면 수가 10배가 된다.하지만 chance!를 외치면 목이 너무 아프기 때문에 우찬이는 chance! 마법을 최대 한 번만 사용할 수 있다. 그리고 마법..
문제 링크: xxx 문제음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다. 입력첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. 출력첫째 줄에 N번째 감소하는 수를 출력한다.풀이접근법완전탐색으로 접근하면 시간초과가 난다.숫자가 계속 감소하는, 순열이기 때문에 최대 9876543210이라는 숫자가 만들어진다. == 배열로 접근한다면 최대 10개의 숫자가 나오게 된다.배열의 ..
문제 링크: https://www.acmicpc.net/problem/9077 문제지뢰제거를 위해서 새로운 장비가 투입되었다. 이 장비를 이용하면 10m × 10m 정사각형 범위 안(경계 포함)에 있는 지뢰를 한꺼번에 제거할 수 있다. 10,000m × 10,000m의 작업장에 묻힌 지뢰의 위치를 모두 알고 있다고 할 때, 이 장치를 효과적으로 사용하기 위해서 한 번 사용하여 제거할 수 있는 최대 지뢰 개수를 계산하는 프로그램을 작성하시오. 위의 그림은 아래 "예제 입력"의 세 번째 경우를 나타낸 것이다. 그림에서 보이는 정사각형 영역에 이 장비를 사용하면 다섯 개의 지뢰를 한꺼번에 제거할 수 있으며, 이 수가 한 번 사용하여 제거할 수 있는 최대 지뢰 개수이다. 입력입력의 첫 줄에는 테스트 케이스의 ..
문제 링크: https://www.acmicpc.net/problem/2660 문제월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이 모임은 만들어진지 얼마 되지 않았기 때문에 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다.예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.4점, 5점 등은 같은 방법으로 정해진다. 각 회원의 점수를 정할 때 주의할 점은 어떤 두 ..
문제 링크: https://www.acmicpc.net/problem/22116 문제창영이의 퇴근길은 출근길과 조금 다르다. 창영이는 건강을 위해 따릉이를 빌려 타고 퇴근하는 습관을 기르고 있다.창영이의 퇴근길은 N×N 크기의 격자로 표현된다. 창영이는 A1,1에서 출발하여 AN,N까지 이동할 계획이다. 창영이는 상하좌우 인접한 격자로 한 번에 한 칸씩 이동할 수 있다. 각 격자 Ar,c에는 자연수가 적혀 있는데, 이는 해당 지역의 높이를 뜻한다. 인접한 격자 사이의 높이 차이의 절댓값을 경사라고 하고, 경사가 클수록 경사가 가파르다고 하자.따릉이는 가격에 따라 성능이 다르다. 비싼 따릉이는 경사가 가파르더라도 내리지 않고 타고 갈 수 있지만, 값싼 따릉이는 경사가 가파르면 힘들고 위험하기 때문에 내려서..
문제 링크: https://www.acmicpc.net/problem/17485 문제우주비행이 꿈이였던 진우는 음식점 '매일매일싱싱'에서 열심히 일한 결과 달 여행에 필요한 자금을 모두 마련하였다! 지구와 우주사이는 N X M 행렬로 나타낼 수 있으며 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다.[예시]진우는 여행경비를 아끼기 위해 조금 특이한 우주선을 선택하였다. 진우가 선택한 우주선의 특징은 아래와 같다.1. 지구 -> 달로 가는 경우 우주선이 움직일 수 있는 방향은 아래와 같다.2. 우주선은 전에 움직인 방향으로 움직일 수 없다. 즉, 같은 방향으로 두번 연속으로 움직일 수 없다.진우의 목표는 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느위치든 착륙하는 것이다..
문제 링크: https://www.acmicpc.net/problem/5214 문제아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까? 입력첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫자는 그 하이퍼튜브가 서로 연결하는 역의 번호이다. 출력첫째 줄에 1번역에서 N번역으로 가는데 방문하는 역의 개수의 최솟값을 출력한다. 만약, 갈 수 없다면 -1을 출력한다.풀이접..
문제 링크: https://www.acmicpc.net/problem/9213 문제완전수는 자기 자신을 제외한 약수의 합이 자기 자신이 되는 자연수이다. 예를 들어, 6의 약수는 1, 2, 3인데 1+2+3은 6이기 때문에 완전수이고, 28도 1+2+4+7+14 = 28이기 때문에 완전수이다.어떤 자연수의 나쁨이란 자기 자신을 제외한 약수의 합과 자기 자신과의 차이이다.꽤 좋은 수는 자연수의 나쁨이 어떤 특정한 값보다 크지 않은 수이다. 예를 들어, 나쁨을 2까지 허용한다면, 100보다 작은 수 중에 꽤 좋은 수는 11가지 2, 3, 4, 6, 8, 10, 16, 20, 28, 32, 64)가 있다. 이 나쁨의 기준을 0으로 바꿔버리면 완전수의 정의와 같아진다.허용하는 나쁨의 최댓값이 주어졌을 때, 꽤 ..