https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 오랜만에 푸는 거라 간단한 문제로 풀어보았습니다. A와 B를 비교할 때 A에 x2 또는 A + "1" 을 하여 B를 몇 번만에 만들 수 있는 지 구하는 문제입니다. 간단하게 bfs를 이용하여 풀었습니다. A를 x2, +"1" 2가지에 대해 계속 탐색하면서, B와 일치하는 경우가 처음 나오면 그 경우가 답입니다. x2, +"1" 을 하여도 B보다 작은 경우, 계속 탐색을 이어가고, 그렇지 않으면 탐색을 거기서는 멈춥니다. 코드는 다음과 같습니다. #include #include #include #include #includ..
https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 뭔가 쉬울 거 같으면서도 될 거 같은 경우가 많았던 문제입니다. 저는 우선순위 큐를 이용해 풀었습니다. 먼저 각 입력으로 들어오는 값들을 정렬하고 (20만 개니까 n log n 인 걸로) 정렬 시 시작 시간이 빠른 순으로 정렬합니다. 그리고 우선순위 큐는 오름차순으로 세팅합니다. 우선순위 큐에 들어 가는 값은 각 수업이 끝나는 시간입니다. 이렇게 하는 이유는 우선 순위 큐의 top 값이 결국 가장 빨리 끝나는 시간을 의미하며, 시작 시간이 빠른..
https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net x1, y1 부터 x2, y2 까지의 합을 구하는 문제입니다. 얼핏보면 n이 최대 1024라 그냥 다 더하면 될 거 같지만 100000번 수행해야 하므로 브루트포스로는 안 됩니다. dp를 이용해 1,1부터 x,y까지의 합을 먼저 구하면 다음과 같습니다. dp[i][j] = num + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] (..
https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 5 x 5 숫자판을 돌아다니면서 6자리 수를 만들 수 있는 경우의 수를 구하는 문제입니다. 조건으로 중복해서 같은 위치를 지날 수 있음에 주의해야 합니다. 판 자체가 5 x 5로 작은 편이므로 특별한 조건 없이 bfs를 진행할 수 있습니다. bfs를 통해 각 위치를 출발점으로 6자리를 계속 만들어가면서 6자리가 만들어졌을 때 set에 넣습니다. 그러면 s..
https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net A,B로만 이루어진 문자열이 주어졌을 때 1. 문자열 뒤에 A 붙이기 2. 뒤집고 B 붙이기 2가지 연산이 가능합니다. 이 때 주어진 문자열 S로 T를 만들 수 있는지 확인하는 문제입니다. 문제를 반대로 생각하면, T의 마지막이 A이면 A를 떼버리고, 마지막이 B이면 떼고 뒤집으면 됩니다. 그리고 S와 비교하여 같은지 아닌지 판단하면 됩니다. 코드는 다음과 같..