AlKon

본 글은 건국대학교 알고리즘 동아리 AlKon 스터디 5조에서 진행된 발표 내용입니다. 2517 달리기 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 시간 제한 입력 범위 1초 N, 기량 3 ≤ N ≤ 500,000 // 1 ≤ 기량 ≤ 1,000,000,000 N: 선수의 수 N개의 줄: 각 선수들의 평소 실력을 앞에서 달리고 있는 선수부터 제시 참가한 선수들의 평소 실력은 모두 다르다. 접근법 세미나에서 들은 내용은 아래와 같다. 기량의 최댓값은 1,000,000,000이므로 이 범위로는 세그먼트 ..

본 글은 건국대학교 알고리즘 동아리 AlKon 스터디 5조에서 진행된 발표 내용입니다. 2458 키 순서 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 시간 제한 입력 범위 1초 N, M, a, b 2 ≤ N ≤ 500 // 0 ≤ M ≤ N(N-1)/2 N: 학생의 수 M: 키를 비교한 회수 a, b: a번 학생이 b번 학생보다 키가 작다. 문제: 자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력하라. 접근법 아직 문제만 보고 알고리즘을 떠올리는 게 쉽지가 않아서 플로이드-워셜을 어떻게 써..

본 글은 건국대학교 알고리즘 동아리 AlKon 스터디 5조에서 진행된 발표 내용입니다. 11060 점프 점프 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 시간 제한 입력 범위 1초 N, A(N개의 수) 1 ≤ N ≤ 1000 // 1 ≤ A ≤ 100 1xN 크기의 배열에서, i 번째 칸에 적힌 수를 Ai 라고 할 때, 해당 칸에서 오른쪽으로 Ai칸 이하만큼 점프할 수 있다. 가장 왼쪽 끝에서 오른쪽 끝으로 갈 때, 점프 횟수의 최솟값을 구하여라. 접근법 점프 횟수의 최솟값을 구해야 하므로, dp..