본문 바로가기

전체 글

 (76)
[백준/C++] 7576번. 토마토 문제 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 1. 마지막 풀이 사고 과정 그냥 BFS 돌리면 되지 않을까? 칸도 1,000 x 1,000으로 널널한데. 토마토 입력, 익은 토마토는 바로 큐에 넣는다. 이때 시간도 함께 체크해둔다. 익은 토마토를 꺼내, 4방향 토마토를 익히고 큐에 넣는다. 모든 토마토가 익었는지 검사한다. 코드 #include #include #include #include int n, m; std::vector tomato; bool promise(int x, int..
[백준/C++] 1132번. 합 문제 1132번: 합 N개의 수가 주어진다. 이 숫자는 모두 자연수이고, 알파벳 A부터 J가 자리수를 대신해서 쓰여 있다. 이 알파벳은 모두 한 자리를 의미한다. 그리고, 각 자리수는 정확하게 알파벳 하나이다. 0으로 www.acmicpc.net 1. 첫 번째 풀이 사고 과정 보자마자 상당히 그리디한데? 라고 생각했고, 생각 그대로 코드로 옮겼다. 우선 각 알파벳은 한 자리의 숫자에 대응된다. 그러니, 가장 비중이 큰 값부터 9, 8, 7... 하며 주는 게 올바른 답을 도출할 것이다. 그럼 비중 계산은 어떻게 하는가? 입력으로 들어온 문자열(하나)에 대해, 해당하는 알파벳에 자릿수(1, 10, 100 등)를 저장한다. ABC, BCA를 예로 들면 ABC에서 A = 100, B = 10, C = 1을 저..
[백준/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 낮춰 다시 시도한다...

티스토리툴바