본문 바로가기

Algorithms/PS

 (29)
[PS] 백준 #2012. 등수 매기기 문제 정보 난이도: 실버 III 문제 주소: https://www.acmicpc.net/problem/2012 이 문제를 푼 이유: 그룹 연습 Div.2 문제 2007년 KOI에 N명의 학생들이 참가하였다. 경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다. KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다. 1등부터 N등까지 동석차 없이 등수를 매겨야 하는 김 조교는, 어쩔 수 없이 각 사람이 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다. 자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 될 경우, 이 사람의 불만도는 A와 B의 차이 (|A - B|)로 수치화할 수 있다. 당신은 N명..
[PS] 백준 #21313. 문어 문제 정보 난이도: 브론즈 II 문제 주소: https://www.acmicpc.net/problem/21313 이 문제를 푼 이유: 그룹 연습 Div. 2 문제 문어에게 여덟개의 팔이 있다는 사실은 잘 알려져 있다. 하지만 문어들이 자신의 팔들을 1번, 2번, 3번, ..., 8번이라고 부른다는 말은 오늘 처음 들었을 것이다! 단, 시계방향으로 오름차순이라던가 하는 규칙은 없다. (물론 그러한 문어도 존재할 수 있다.) 문제에선 편의상 팔 대신 손이라고 부르자. 문어들은 정월 대보름을 맞아 강강술래를 하려고 한다. 각 문어는 양 옆의 서로 다른 두 문어와 손을 맞잡아 원을 만든다. 문어끼리 손을 잡을 때 지켜야 할 예절이 있다. 서로 같은 번호의 손을 잡아야 한다. 한 문어와 둘 이상의 손을 잡을 수 ..
[PS] 백준 #21968. 선린의 터를 문제 정보 난이도: 실버 IV 문제 주소: https://www.acmicpc.net/problem/21968 이 문제를 푼 이유: 그룹 연습 Div.2 문제 드높은 남산 위에 우뚝 선 (중략) 세워라 반석 위에 선린의 터를 1899년, 여러분들은 대한제국 고종 황제의 칙령을 받아 한국 최초의 실업교육기관인 관립상공학교를 세울 터를 선택해야 한다. 대한제국에서 학교를 지을만한 터는 여러 개 있는데, 각 터는 서로 다른 자연수를 번호로 갖고 있다. 특히, 선린의 터의 번호는 $3^k$꼴의 자연수가 최대 한 번씩 더해진 자연수이다(단, $k \ge 0$). 즉, 선린의 터의 번호는 $1(=3^0), 3(=3^1), 9(=3^2), 27(=3^3), 81(=3^4), 90(=3^2+3^4), 91(=3^0+3..
[PS] 백준 #21966. (중략) 문제 정보 난이도: 실버 V 문제 주소: https://www.acmicpc.net/problem/21966 이 문제를 푼 이유: 그룹 연습 Div.2 문제 드높은 남산 위에 우뚝 선 (중략) 세워라 반석 위에 선린의 터를 1개 이상의 문장들이 주어진다. 아래 규칙에 따라 문장들의 중간 부분을 적당히 생략해 25글자 이내로 요약해서 출력하는 프로그램을 작성하자. 단, 입출력의 편의를 위해 문장들을 공백 없이 모두 붙여 구성한 문자열 S$S$가 대신 주어진다. 문자열의 첫 글자부터 가장 먼저 만나는 '.'(마침표)까지, 그리고 각 '.'의 다음 글자부터 가장 먼저 만나는 '.'까지를 한 문장으로 생각하기로 하자. 예를 들어 주어진 문자열 $S$가 'IamInevitable.IamIronMan.'이라면 'I..
[PS] 백준 #1708. 볼록 껍질 문제 정보 난이도: 플래티넘 V 문제 주소: https://www.acmicpc.net/problem/1708 이 문제를 푼 이유: 300번째 문제 기념 문제 다각형의 임의의 두 꼭짓점을 연결하는 선분이 항상 다각형 내부에 존재하는 다각형을 볼록 다각형이라고 한다. 아래 그림에서 (a)는 볼록 다각형이며, (b)는 볼록 다각형이 아니다. 조금만 생각해 보면 다각형의 모든 내각이 180도 이하일 때 볼록 다각형이 된다는 것을 알 수 있다. 편의상 이 문제에서는 180도 미만인 경우만을 볼록 다각형으로 한정하도록 한다. 2차원 평면에 N개의 점이 주어졌을 때, 이들 중 몇 개의 점을 골라 볼록 다각형을 만드는데, 나머지 모든 점을 내부에 포함하도록 할 수 있다. 이를 볼록 껍질 (CONVEX HULL) 이라..
[PS] 백준 #14502. 연구소 문제 정보 난이도: 골드 V 문제 주소: https://www.acmicpc.net/problem/14502 이 문제를 푼 이유: 브루트포스 연습 문제 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. 예를 들어, 아래와 같이 연구소가 생..
[PS] 백준 #21937. 작업 문제 정보 난이도: 실버 I 문제 주소: https://www.acmicpc.net/problem/21937 이 문제를 푼 이유: 그룹 연습 Div 2 문제 민상이는 자신이 해야할 작업 $N$개를 아래와 같이 작업 순서도로 그려보았다. 위 그림에서 5번 작업을 하기 위해 제일 먼저 2번 작업을 끝내야 하고 그 다음으로 4번 작업을 끝내야 5번 작업을 할 수 있다. 3번 작업은 먼저 해야하는 작업이 없으므로 3번 작업을 바로 시작 할 수 있다. 작업 순서를 정할때 위배되는 작업 순서는 없다. 예를 들어, A 작업을 하려면 B 작업을 먼저 해야하고, B 작업을 해야하기 전에 A 작업을 해야하는 상황은 없다. 민상이는 오늘 반드시 끝낼 작업 $X$가 있다. 민상이가 작업 $X$ 을 끝내기 위해서 먼저 해야하는..
[PS] 백준 #16564. 히오스 프로게이머 문제 정보 난이도: 실버 I 문제 주소: https://www.acmicpc.net/problem/16564 이 문제를 푼 이유: 그룹 연습 Div 2 문제 성권이는 Heroes of the Storm 프로게이머 지망생이다. 이 게임에는 총 N개의 캐릭터가 있다. 그리고 현재 각 캐릭터의 레벨은 Xi이다. 성권이는 앞으로 게임이 끝날 때까지, 레벨을 최대 총합 K만큼 올릴 수 있다. 팀 목표레벨 T =min(Xi) (1 ≤ i ≤ N)라고 정의하면, 게임이 끝날 때까지 성권이가 달성할 수 있는 최대 팀 목표레벨 T는 무엇인가? 예를 들어, N = 3, X1= 10, X2= 20, X3= 15이고 K = 10일 때, X1을 7만큼 올리고 X3을 2만큼 올리면 최소 레벨 Xi는 17이 된다. 따라서 팀 목표..

티스토리툴바