본문 바로가기

분류 전체보기

 (72)
[백준/C++] 1005번. ACM Craft 문제 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 1. 마지막 풀이 사고 과정 위상정렬 공부하려고 집은 문젠데, DP 개념도 섞여 있는 문제. 둘을 동시에 진행할 수도 있지만, 내가 아직 위상정렬이 미숙해서 따로따로 구현하기로 했다. 알고리즘 이 문제는, 특정 건물을 지으면 다음 건물을 지을 수 있는 시스템에서 시작된다. 내가 특정 건물(예제 1의 4)을 짓고 싶은데, 이 건물을 가장 빠르게 짓는 방법을 알고 싶다. 건물을 짓기 위해선 선행 건물들을 모두 지어야 한다. 하지만 일꾼의 수는 무한해서, ..
[백준/C++] 15486번. 퇴사 2 문제 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 1. 첫 번째 풀이 사고 과정 이번에도 DP 문제. 특정 날에 시작, T일 후 끝나는 상담 진행 시 P원을 받는다. 퇴사까지 N일이 남았을 때, 최대한 돈을 버는 방법을 구하는 문제. 이번에도 저번 문제, 점프 점프와 비슷하게 생각하고, 빠르게 코드를 짜 제출했다. 간단히 알고리즘을 설명하자면 0일부터 N일까지 크게 반복(i) i일에 상담을 시작하면 i + t[i]일부터 P[i]원을 받을 수 있다. 그러니 i + t[i]일 부터..
[백준/C++] 11060번. 점프 점프 문제 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 1. 마지막 풀이 사고 과정 대학 알고리즘 수업 시험 문제였으면서, 자력으로 풀어 A+를 받게 해준 고마운 문제. 그래서 더 인상깊게 남은 문제다. DP엔 크게 탑다운(정답 칸부터 점화식 계산 시작, 구한 적 없다면 재귀적으로 계산) 방식과 바텀업(가장 작은 칸부터 순차적으로 점화식을 계산, 정답 칸이 계산되면 반환하며 종료) 방식이 있다. 문제의 구조 상 숫자가 큰 칸에서, 자신..
[백준/C++] 1038번. 감소하는 수 문제 https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 1. 첫 번째 풀이 사고 과정 가장 단순한 방법은 이렇게다. 인덱스 i와 수 k 변수를 정의해둔다. i를 0부터 N까지 반복한다. k가 감소하는 수라면 i와 k를 모두 증가 k가 감소하는 수가 아니라면 k만 1 증가, 다시 반복 간단히 코드로 써보면 아래와 같다. 코드 #include #include using ll = long long; // 감소하는 수 판정 bool isD..
[백준/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] +..

티스토리툴바