본문 바로가기

Algorithm

 (640)
[2017 홍익대학교 프로그래밍 경진대회] 14923번 미로 탈출 문제 홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 있어 홍익이가 탈출하기 어렵게 하고 있다. 홍익이는 마법사의 연구실에서 훔친 지팡이가 있어, 벽을 길로 만들 수 있다. 그렇지만, 안타깝게도 마법의 지팡이는 단 한 번만 사용할 수 있다. 이때, 홍익이를 도와 미로에서 탈출할 수 있는지 알아보고, 할 수 있다면 가장 빠른 경로의 거리 D는 얼마인지 알아보자. 인접한 칸으로 이동하는데 똑같은 시간이 들고, 벽을 부수는 데 시간이 걸리지 않는다. 입력 N M Hx Hy Ex Ey N X M 행렬 2 ≤ N ≤ 1000, 2 ≤ M ≤ 1000 1 ..
[2017 홍익대학교 프로그래밍 경진대회] 14922번 부분평균 문제 A를 길이 N인 양의 정수로 구성된 배열이라고 하자.(N>2) 정수 P, Q(0 temp) { mina = temp; idx = i - 1; } } cout
[2017 홍익대학교 프로그래밍 경진대회] 14921번 용액 합성하기 문제 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당신은 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 하는데, 각 용액은 10ml시험관에 10ml씩 들어있고, 빈 20ml 시험관이 단 하나 있다. 게다가 용액을 계량할 수 없어서, 두 용액을 섞을 때는 10ml씩 섞어서 20ml로 만드는데, 단 한번밖에 할 수 없다. 그래서 미리 용액의 특성값들을 보고, 어떤 두 용액을 섞을 것인지 정해야 한다. 예를 들어, 연구소에 있는 용액들의 특성값이 [-101, -3, -1, 5, 93]이라고 하자. 이 경우에 특성 값이 각각 -10..
[2018 홍익대학교 프로그래밍 경진대회] 16401번 과자 나눠주기 문제 명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다. 조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다. 그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리 싸움이 일어난다. 따라서 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다. M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라. 단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다. 입력 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N..
[2018 홍익대학교 프로그래밍 경진대회] 16400번 소수 화폐 문제 소수나라는 특이하게 모든 소수(prime number)를 화폐 단위로 사용한다. 소수나라에 놀러 온 하나는 관광을 하다가 가격이 N인 물건을 발견하고 너무 마음에 들어 999983원을 내고 구매하려고 했다. 하지만 상점 주인이 거스름돈이 없어 정확히 N원을 지불해달라고 하였다. 물건을 구매하려던 하나는 소수나라의 화폐를 이용하여 N원을 정확히 만들 수 있는 방법의 가짓수가 얼마나 되는지 궁금해졌다. 하나를 도와 N원을 지불하기 위한 가짓수가 얼마나 되는지 구해보자. 단, 하나는 소수나라의 모든 화폐가 무한정 있다고 가정한다. 입력 구매하려고하는 물건의 값 N(2 ≤ N ≤ 40,000, N은 정수)이 주어진다. 출력 소수나라의 화폐를 이용하여 지불할 수 있는 방법의 수를 출력한다. 단, 지불할 수 ..
[2018 홍익대학교 프로그래밍 경진대회] 16397번 탈출 문제 홍익이는 홍익대학교 프로그래밍 경진대회의 출제진이다. 홍익이는 새벽에 문제를 만들던 도중 뒤통수에 느껴지는 고통과 함께 정신을 잃었다. 홍익이는 좁은 방에서 눈을 떴다. 주변을 살펴보니 벽면에는 LED로 된 다섯 자리 십진수 N이, 그 옆에 T, G라는 알파벳과 함께 또 다른 정수 두 개가 쓰여 있었고, 벽 앞에는 버튼 A, B 두 개가 있었다. 버튼을 이리저리 눌러보던 똑똑한 홍익이는 어떻게 해야 방을 탈출할 수 있을지 금방 눈치챘다. 버튼과 수에 대해 홍익이가 알아낸 것은 다음과 같다. 버튼 A를 누르면 N이 1 증가한다. 버튼 B를 누르면 N에 2가 곱해진 뒤, 0이 아닌 가장 높은 자릿수의 숫자가 1 줄어든다. 예를 들어 123→146으로, 5→0으로, 3→5로 변한다. 단, N이 0이면 버..
[2018 홍익대학교 프로그래밍 경진대회] 16396번 선 그리기 문제 준용이의 조카 준섭이는 크레파스로 한 직선에 평행한 여러 개의 선분을 그리고 있었다. 준섭이의 모습을 보고 있던 준용이는 준섭이가 그린 모든 선들을 직선 좌표에 투사(projection)했을 때 투사된 선들의 길이 합이 궁금하였다. 준용이에게 잘 보여야하는 여러분은 준용이의 궁금증을 해결하기 위해 프로그램을 구현해주자. 입력 첫 번째 줄에는 준섭이가 그린 선의 개수 N이 입력된다. 두 번째 줄부터 N+1 번째 줄까지는 준섭이가 그린 선의 시작 좌표 Xi와 끝 좌표 Yi 가 순서대로 주어진다. Xi 와 Yi 는 정수이며, 띄어쓰기로 구분된다. N의 범위는 1부터 10,000까지이다. 선의 시작 좌표와 끝 좌표는 1부터 10,000까지의 자연수이다. 출력 직선 좌표에 투사된 선의 총 길이 합을 정수로 ..
[2018 홍익대학교 프로그래밍 경진대회] 16395번 파스칼의 삼각형 문제 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행에는 N개의 수가 있다. 첫 번째 행은 1이다. 두 번째 행부터, 각 행의 양 끝의 값은 1이고, 나머지 수의 값은 바로 위 행의 인접한 두 수의 합이다. 예를 들어, n=3이면 3번째 행의 2번째 수는 위 행의 인접한 두 수 (1과 1)을 더해서 만든다. n=6일 때, 파스칼 삼각형의 6번째 행의 10은 5번째 행의 인접한 두 수(4와 6)을 더해서 구한다. 같은 방식으로 n=11일 때, 다음과 같은 파스칼의 삼각형을 만들 수 있다. 정수 n과 k가 주어졌을 때 파스칼의 삼각형에 있는 n번째 행에서 k번..

티스토리툴바