본문 바로가기

코딩테스트/백준

 (34)
[백준/C++] 1644번. 소수의 연속합 문제 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 1. 마지막 풀이 사고 과정 연속된 소수의 합으로 표현하기? 배열에서 시작과 끝 인덱스를 지정해두고, 다 더한 게 n보다 작으면 끝을 한 칸 이동, n보다 크면 시작을 오른쪽으로 한 칸 이동. 2-Sum 알고리즘이 작동하듯 움직이면 될 것 같았다. 그런데 경우의 수를 세는 문제네? 그럼 찾았을 때 출력 대신 count를 증가시키고, 시작 인덱스를 옮기며 다시 진행하자. 탈출 조건을 정해줘야 한다. 시작 인덱스가 끝 인덱스를 넘어가면 끝나지 않을까? 그럼 이제 필요한 건 소수만 모아둔 배열. 이전 뻘짓 땐 노가다로 했었는데, 이번엔 에라토스테네스의 체로 만들어 보자. [Algo..
[백준/C++] 10844번. 쉬운 계단 수 문제 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1. 마지막 풀이 사고 과정 어려운 문제를 풀려면, 쉬운 문제부터 풀어봐야 한다. 비트마스킹과 DP를 이용한다고 알려진 계단 수 문제를 풀기 전에, 쉬운 계단 수가 있길래 풀어봤다. 문제는 간단하다. 인접한 자리끼리 1씩만 차이나는 수를 계단 수라고 할 때, n자리 계단 수는 총 몇 개인가? 이친수 문제와 비슷하게, 끝자리 마다 숫자 개수를 저장해놓고 더하는 방식을 사용했다. 2차원 배열 grid 선언, 크기는 [n + 1][10] grid[1]을 초기화. 0은 0, 나머진 1. 이후 배열들은 앞의 값을 이용해 계산. 예를 들어 grid[3][4]는 grid[2][3] +..
[백준/C++] 1107번. 리모컨 문제 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 www.acmicpc.net 1. 첫 번째 풀이 사고 과정 이 문제는 옮길 수 있는 채널을 하나 구해서 채널을 옮기고, 거기서 +, -를 조작해 원하는 채널을 만드는 문제다. 예를 들어 5457번 채널을 맞추는데 6, 7, 8번이 고장났다면 5455번으로 이동한 후 +를 2번 누르면, 6번 버튼을 눌러 이동할 수 있다. 버튼을 누르는 최소 횟수를 구해야 했기에, 반대로 답에서부터 거슬러 올라가기로 했다. 위와 같은 예시를 살펴보자. 먼저 5457로 옮길 수 있는지 검..
[백준/C++] 2193번. 이친수 문제 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 1. 첫 번째 풀이 사고 과정 자릿수를 인덱스로 하는 DP가 바로 떠올랐다. 앞선 자리의 수가 0으로 끝났다면, 0과 1 두 가지를 붙일 수 있다. 반대로 1로 끝났다면, 오직 0만 붙일 수 있다. 0으로 끝난 수의 개수와 1로 끝난 수의 개수가 필요했기에, 둘을 따로 나눠 두 개의 벡터를 쓰기로 했다. 두 벡터 end0, end1을 생성, end0은 0, end1은 1로 초기화 end0[i] = end0[i - 1] + end1[i - 1] e..
[백준/C++] 1010번. 다리 놓기 문제 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 1. 마지막 풀이 사고 과정 DP로 풀면 쉽게 풀릴 것 같았다. 조합의 특성이 딱 맞기 때문에. 조합의 계산식을 예시와 함께 살펴보겠다. 6C2는 식으로 쓰면, 위와 같이 쓰인다. 이건 이 식을 변형한 것으로, n!을 (n - r)!로 약분해서 만든 형태다. 그럼 7C2는 어떻게 표현될까? 7C2는 위처럼 표현된다. 마지막 숫자가 나눠지고, n이 그대로 곱해진다. 이를 좀 더 수학적으로 표현해보면 아래처럼 나타난다. 이는 그대로 DP로 구현된다. 바로 코드..
[백준/C++] 1082번. 방 번호 문제 https://www.acmicpc.net/problem/1082 1082번: 방 번호 첫째 줄에 N이 주아진다. 둘째 줄에는 공백으로 구분된 P0, ..., PN-1이 주어진다. 마지막 줄에는 M이 주어진다. www.acmicpc.net 1. 첫 번째 풀이 사고 과정 방 번호의 크기에 가장 크게 영향을 끼치는 건 자릿수며, 그 다음이 (앞쪽부터) 숫자의 크기다. 단순하게는 자릿수를 최대한 늘린 뒤, 첫 자리부터 그리디하게 업그레이드 해나가면 될 것 같다. 데이터 입력, 비용의 최솟값을 미리 구해둔다. 각 번호의 비용에서 최소 비용을 뺀다. 이는 곧, 숫자를 업그레이드 비용하는 게 된다. 가장 큰 번호부터 구매를 시도한다. 만약 계산이 끝난 후, 첫 자리가 0이라면 자릿수를 1 낮춰 다시 시도한다...
[백준/C++] 1193번. 분수찾기 문제 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 1. 첫 번째 풀이 사고 과정 - 대각선이지만 굳이 대각선으로 볼 필욘 없다. 1/1을 한 줄, 1/2와 2/1을 한 줄, 1/3과 2/2와 3/1을 한 줄. 이렇게 계단처럼 쌓을 수 있다. - 우린 각 줄의 첫번째, 즉 1/N이 몇 번째부터 시작하는지 알 수 있다. 1, 2, 4, 7, 11. 정확히는, 해당 줄의 앞이 몇 번으로 끝났는지 알 수 있다. 0, 1, 3, 6, 10, 15, 21. 익숙한 1부터 n까지의 합. 이 번호들을 기준 번호라고 하자. - 그러니 우선 1부터 더해가며, X를 넘지 않는 값까지 더하면, 마지막에 더한 값으로부터 N을 알 수 있다. 만약 12라면 10에..
[백준/C++] 1083번. 소트 문제 1083번: 소트 크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전 www.acmicpc.net 1. 첫 번째 풀이 사고 과정 - 시간 제한은 널널한 편. 배열을 전부 검사해보고 큰 수를 한 칸 전진시켜도 충분한 시간이다. - 예제들로 살펴보면, 앞에서부터 검사하며 뒤의 수가 더 클 때 자리를 교환하면 될 것 같다. - 하지만 굳이 사전순으로 뒷선다고 조건을 건 걸 보면, 배열 내 원소의 자릿수가 다른 경우도 감안해야 할 것 같다. - 자릿수가 같다면 그냥 큰 수를 올리면 된다. 96과 89면 96이 앞서면 된다. 하지만 919와 99라면, 99가..

티스토리툴바