26876번: New Time Nikolay has a digital clock that displays time in 24-hour format, showing two integers: hours (from $00$ to $23$) and minutes (from $00$ to $59$). For example, the clock can show 00:00, 18:42, or 23:59. The clock has two buttons that can be used for manual www.acmicpc.net 문제 이해 & 기본 개념 잘못된 시간과 정확한 시간이 주어지고, 1분씩 증가하는 A버튼, 1시간씩 증가하는 B버튼이 있다. 버튼을 최소 횟수로 눌러서 정확한 시간에 맞추는 문제 중요 포인트 시간..
2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 먼저 풀어보면 좋을 문제 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 문제 이해 & 기본 개념 세 용액의 합이 최소가 되는 경우를 구하는 문제 용액(2467번) 문제에서 하나의 용액이 더 추가 되었다. 용액(2467번) 문제는 투 포인터..
2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 이해 & 기본 개념 계단은 1~2칸 씩 이동할 수 있다. 3칸을 연속으로 밟아선 안된다. 마지막 계단은 반드시 밟아야한다. 위의 조건에 한해서 계단을 밟았을 때 받을 수 있는 가장 높은 점수를 구하는 문제 중요 포인트 해당 문제에서의 중요 포인트는 아래와 같다. 맨 뒤에서부터 시작 문제 조건에서 마지막 계단은 무조건 밟아야한다고 명시되어 있다. 시작점을 마지막 계단으로 놓고 내려가는 방식으로 구현하면 쉽다. 연속으로 3개의 계단을 밟는 경우 판별 이전에 몇 칸을 뛰어서..
10812번: 바구니 순서 바꾸기 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다. 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2 www.acmicpc.net 문제 이해 & 기본 개념 1 ~ N 까지의 원소가 있는 배열이 존재 begin ~ end 구간에서 mid를 기준으로 앞뒤를 바꾸는 문제 중요 포인트 스왑을 이용하면 배열 하나로 풀 수 있다. 최종 풀이 mid ~ end의 원소를 스왑을 통해 앞으로 가져올 예정 범위의 마지막 원소부터 시작해서 범위의 맨 앞으로 끌어다 놓는다. mid ~ end 사이의 원소를 begin까지 swap하는 방식으로 반복하면 됨 최악의 경우는 구간이 1 ~ N이고 mid가 1..
1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 이해 & 기본 개념 특정 노드 2개를 잡고 양쪽으로 당겼을 때, 가장 길게 늘어나는 경우를 트리의 지름이라 한다. dfs를 수행해서, 각 노드의 자식들 중 가장 큰 가중치 + 자신의 가중치를 리턴한다. 갈라지는 부분에선, 해당 노드가 중심이 될 수 있는 가능성이 있기에, 자식들의 가중치의 합 중 가장 큰 2개를 구해서 max와 비교한다. 양쪽으로 잡아 당길 때, 두 개를 잡고 당기기 때문에 상위 가중치 2개를 선택 중요 포인트 이진 트리..
9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제 이해 & 기본 개념 n 명의 학생이 각각 같이 팀이 되고 싶은 학생을 1명씩 선택한다. 학생들을(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다. 학생들이 선택한 결과가 주어질 때, 팀에 속하지 않는 학생의 수를 구하는 문제 중요 포인트 선택한 학생들끼리 사이클을 이루는 경우가 팀이 되는..
2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 문제 이해 & 기본 개념 스도쿠를 완성시키는 문제 시간 제한이 2초로 충분하므로 백트래킹을 이용하면 쉽게 풀 수 있다. 중요 포인트 가로, 세로, 3x3 사각형에서 중복되는 숫자가 없는지 확인해야한다. 가로, 세로에선 아래와 같이 쉽게 확인할 수 있다. map[x][y]와 for문의 위치가 같아지는 경우 continue로 처리해버리면, 세로의 경우를 체크하지 못할 수 있다. // map[x][y]와 중복되는 숫자가 있는지 체크하는 for문 for (i in..
2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 문제 이해 & 기본 개념 배열의 원소 중 2개의 합이 0에 가장 가까운 원소 쌍을 찾는 문제 투 포인터를 이용하면 쉽게 구할 수 있다. 중요 포인트 두 개의 포인터를 양 쪽 끝에서 시작하는게 포인트 최종 풀이 두 개의 포인터를 각각 배열의 맨 앞과 맨 뒤에 배치한다. 왼쪽 포인터를 당기는 경우 or 오른쪽 포인터를 당기는 경우 중 0에 더 가까워 지는 쪽으로 포인터를 이동한다. cur = abs(num[i] + num[j]) // 현재 두 원소의 합 if(..
