블로그 언저리인 무언가

문제 : 17953 디저트 17953번: 디저트 창호는 매일 점심마다 디저트를 먹는다. 그런데 같은 디저트라도 매일 느끼는 맛이 달라진다. 어떤 날에는 마카롱을 먹고 매우 행복함을 느끼는 반면 어떤 날에는 ‘차라리 케이크를 먹는게 나� www.acmicpc.net 각 날마다 디저트가 주는 만족감이 주어질 때, 최대로 얻을 수 있는 만족감을 출력하는 문제이다. 날짜를 N, 디저트의 종류를 M이라 할 때 그냥 모든 경우의 수를 구하면 O(M^N)이므로 당연히 시간 초과가 난다. DP 배열을 만들어 전날까지의 만족감 중 최대를 골라 계속 갱신해주면 O(N*M^2)로 시간제한 안에 해결할 수 있다. Code #include #define ll long long using namespace std; ll N, M..

문제 : 15724 주지수 15724번: 주지수 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 �� www.acmicpc.net 직사각형의 범위가 주어질 때 그 안에 사는 사람 수의 합을 출력하는 문제이다. 배열의 길이가 N, 주어지는 범위의 개수가 M일 때 그냥 구하게 되면 O(N^2*M)으로 시간 초과이므로 누적합 배열을 이용해 시간을 O(N^2+M)으로 줄여서 구하면 된다. Code #include #define ll long long using namespace std; ll N, M, T, arr[1050][1050]; int main(){ ios::sy..

문제 : 1342 행운의 문자열 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작� www.acmicpc.net 어떤 문자열이 주어졌을 때 문자를 재배치해 인접한 문자가 같지 않은 문자열의 경우의 수를 구하는 문제이다. 문자열을 정렬한 후 next_permutation을 이용해 모든 경우의 수를 확인하면 된다. Code #include #define ll long long using namespace std; string S; ll ans; int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> S;..

문제 : 14499 주사위 굴리기 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 지도의 크기와 각 칸에 쓰여있는 정수가 주어졌을 때, 주사위를 굴리는 명령이 주어질 때 위에서 보이는 면을 출력하는 문제이다. 각 방향으로 이동할 때 각 주사위의 면이 어떻게 회전하는지 알려주는 roll배열을 선언한 후 해당하는 순서로 값의 순서를 바꾸고 해당하는 칸의 명령을 수행하면 된다. Code #include #define ll long long using ..

문제 : 4811 알약 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 매일매일 알약을 꺼내먹었을 때, 전체 조각과 반 조각을 뽑는 순서의 경우의 수를 세 출력하는 문제이다. 남은 알약이 모두 반 조각 짜리라면 문자열이 결정되고, 반 조각짜리 알약이 음수 개인 경우는 불가능하게 처리하여 memoization기법을 활용해 Top-Down 방식의 DP를 짜서 이전 결과 값을 저장해 꺼내서 출력했다. Code #include #define ll long long using namespace std; ll N, M, arr[35][..

문제 : 13703 물벼룩의 생존확률 13703번: 물벼룩의 생존확률 수면에서 k 센티미터 아래에 있는 물벼룩은 1초마다 각각 1/2의 확률로 위 또는 아래로 1 센티미터 이동한다. 물벼룩은 수면에 닿자마자 기다리고 있던 물매암이들에 의해 먹혀 없어진다. 예를 www.acmicpc.net 1초마다 1/2 확률로 위 또는 아래로 이동할 때, 시간이 끝날 때까지 생존해있는 경우의 수를 구하면 된다. 수면에 닿았을 때 남은 움직임과 상관없이 모두 실패하고 남은 움직임 횟수보다 더 깊이 있는 상태에서는 2^횟수만큼 성공하므로 memoization기법을 활용해 Top-Down 방식의 DP를 짜서 이전 결과 값을 저장해 꺼내서 출력했다. Code #include #define ll long long using na..

문제 : 4386 별자리 만들기 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일� www.acmicpc.net 별들의 좌표가 주어졌을 때 각 별들을 모두 잇는 최소 길이를 구해 출력하는 문제이다. 최소 스패닝 트리를 구해야 하므로 UnionFind를 짜고 각 간선에 이어진 점과 간선의 비용을 우선순위 큐에 넣어 가장 적은 비용부터 꺼내며 사이클이 생기지 않게 처리해주면 된다. Code #include #define ll long long using namespace std; typedef pair pdd; struct ABC{ ll a, ..