문제 https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 풀이 순열이 포함된 구현 문제입니다. 처음에는, 점수를 계산하는 과정을 큐로 구현을 했습니다. Base를 돌고 홈으로 오는 선수들을 큐 자료형을 표현했는데 시간 초과가 나서, 점수를 산정하는 과정을 boolean[] 배열을 통해 경우를 따져가는 식으로 변경했습니다. 그리고 순열 시에 1번 타자는 항상 4번 째에 위치하는 것을 고려해, 해당 depth일 때는 배정을 한 칸씩 뒤로 미루었습니다. 아래..
Java
문제 https://www.acmicpc.net/problem/24042 24042번: 횡단보도 당신은 집으로 가는 도중 복잡한 교차로를 만났다! 이 교차로에는 사람이 지나갈 수 있는 $N$ 개의 지역이 있고 그 지역 사이를 잇는 몇 개의 횡단보도가 있다. 모든 지역은 횡단보도를 통해 직, www.acmicpc.net 풀이 다익스트라를 응용한 문제입니다. 일반적인 다익스트라 문제에서는 노드 간의 거리 비용을 가중치로 둡니다. 이 문제에서는 횡단 보도를 건너기 위해 기다려야하는 총 시간을 가중치로 두는 것이 핵심입니다. 특히, 이 문제에서는 M이라는 주기 변수가 있습니다. 그래서 다음 노드로 진행하기전에 이 부분을 체크해주어야합니다. 주기 M을 고려하여 다음 노드로 이동하기 위해 기다려야 하는 시간을 계산..
문제 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 풀이 슬라이딩 윈도우 문제입니다. N의 input size가 30,000이기 때문에 for 문을 2번 돌게 되면 시간 제한 1초를 넘기게 됩니다. 관건은 초밥의 개수가 아닌 종류를 세야하는 것인데, 이는 Map 자료형을 통해 해결했습니다. map에서 key를 초밥의 종류로, value를 종류 당 개수로 지정해주고, 종류 카운트는 map.size를 통해 ..
문제 https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 풀이 슬라이딩 윈도우 기법을 활용한 문제입니다. N의 input size가 250,000이기 때문에 for문을 두 번 돌면 제한 시간인 1초가 훨씬 넘어가게 됩니다. 한 칸씩 이동하며 앞의 칸은 sum에서 빼고, 뒤의 칸은 sum에 더하는 방식으로 슬라이딩 윈도우 기법을 활용했습니다. 그리고 기간이 몇 개인지도 정해야하는데, 이것은 map 자료형을 통해 key를 sum 값으로, 그리고..
문제https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일www.acmicpc.net풀이 전형적인 크루스칼 문제입니다. 가중치 값이 소수라는 것이 조금은 특이합니다. 우선 입력받는 좌표 값을 stars 라는 ArrayList 에 입력받고, 이 값을 edgeList라는 ArrayList에서 연결했습니다. 이 때, 제공되는 좌표를 가중치(거리)로써 필요한 것에 집중하고, 두 쌍의 좌표는 하나의 인덱스(i or j)로 ArrayList에 입력을 해주었습니다. 그렇게 인덱스를 통해 서..
문제 https://www.acmicpc.net/problem/19949 19949번: 영재의 시험 컴퓨터공학과 학생인 영재는 이번 학기에 알고리즘 수업을 수강한다. 평소에 자신의 실력을 맹신한 영재는 시험 전날까지 공부를 하지 않았다. 당연하게도 문제를 하나도 풀지 못하였지만 다행 www.acmicpc.net 풀이 백트래킹을 이용한 문제입니다. 백트래킹 메서드에 매개변수로 찍었는데 맞은 정답의 수, 현재의 인덱스, 찍은 배열을 전달했습니다. 이 때 조건에 따라 정답의 수가 5개가 넘으면 ans++를 통해 답을 구합니다. 그리고 3개 이상 연속된 수를 고를 수는 없다는 조건에 맞게 idx가 2이상일 때는 만약 앞의 idx의 값이 두 번 연속되었다면, 그 수는 다음에서 선택할 수 없도록, ban이라는 변수..
