블로그 언저리인 무언가

#include // gcc에서 대부분의 헤더를 포함하는 헤더파일 #define ll long long //long long 축약 #define INF 1e9+7 // 최대값 #define MOD (ll)(1e9+7) // 나머지계산 using namespace std; typedef pair pll; // pair 축약 // 구조체 만들기 struct Edge{ ll idx, dst; Edge() {} Edge(ll a, ll b): idx(a), dst(b) {} }; struct dice{ ll arr[3][2]; dice() {} dice(ll a, ll b, ll c, ll d, ll e, ll f) : arr{{a,f},{b,d},{c,e}} {} }; // 구조체 비교함수(우선순위 큐에 자주..

문제 : 1753 최단경로 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 방향 그래프가 주어졌을 때, 시작점에서 다른 모든 점까지의 최단경로를 구해 출력하는 문제이다. Dijkstra 알고리즘을 사용해 순회한 후 경로가 존재하는지 체크해 배열의 값을 출력하면 된다. Code #include #define ll long long #define INF 987654321 using namespace std; typedef pair pll; struct ABC { ll idx, dst; ..

문제 : 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][..