본문 바로가기

코딩테스트

 (34)
[백준/C++] 1081번. 합 문제 1081번: 합 L보다 크거나 같고, U보다 작거나 같은 모든 정수의 각 자리의 합을 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 첫 번째 풀이 사고 과정 자릿수는 아래와 같은 특징이 있다. k + 1의 자릿수는 k의 자릿수의 합 + 1이다. 예를 들어 316의 자릿수의 합은 10으로, 315의 자릿수의 합인 9보다 1 큰 값이다. 이를 통해 L부터 U까지, 모든 자릿수의 합의 합을 구할 수 있는데 위와 같은 원리로 구할 수 있다. 하지만 여기엔 함정이 있는데, 이렇게 9 -> 0으로 넘어가는(꺾이는) 부분에서, 자릿수가 -9를 한다는 점이다. (왜 -8이 아닌 -9냐면, 20은 원래 자릿수의 합이 11이어야 하는 자리기 때문.) 그럼, 이런 부분이 몇 개 존재하는가? 14와 5..
[백준/C++] 1793번. 타일링 문제 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 n이 주어진다. www.acmicpc.net https://www.acmicpc.net/problem/2133 이 문제의 좀 더 쉬운 버전. 1. 첫 번째 풀이 사고 과정 매우 단순한 형태의 DP였기에, 간단히 풀었다. 타일은 1x2, 2x1, 2x2가 있다. 행은 2행으로 고정이니, 열만 생각해보자. 1개의 열에 놓을 수 있는 타일 수는 몇 개인가? 1x2 한 개다. 2개의 열엔? 1x2 2개, 2x1 2개, 2x2 1개. 3가지 경우의 수가 있다. 하지만 이 중 1x2를 2개 놓는 건, 1번째 경우의 수(1개의 열에 놓는 경우)와 겹치니 제외한다. 그러니 타일링은 1칸 전 최..
[백준/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을 저..

티스토리툴바