1. 문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 2. 접근 방법 그리디를 떠올릴 수만 있다면 아주 쉬운 문제입니다. 하지만 그리디를 떠올리기 쉽지 않으므로 항상 일관된 알고리즘적 사고가 필요한 것 같습니다. 따라서 평소처럼 일관된 방법으로 접근했습니다. 아이디어 완전 탐색으로 생각해볼 때 나올 수 있는 모든 가지수는 1000!입니다. 팩토리얼의 허용 범위는 11이므로 불가능합니다. 완전 탐색이 불가능하여 DP로 접근해보았습니다. 이 문제의 조건을 보니 조합이 아니..

두 가지 방법으로 접근할 수 있다. 1. LIS를 두번한 다음 비교하기 2. 반복문을 돌며 기준점을 잡고 증가하는 부분 수열과 감소하는 부분 수열을 구한 뒤 최댓값 구하기

#include #include #include #include #define F first #define S second using namespace std; typedef pair PII; int V, E, X; int d1[1001], d2[1001]; vector go[1001], back[1001], temp[1001]; priority_queue pq; const int INF = 1e9 + 10; void dijkstra(vector* g, int* d, int start){ d[start] = 0; pq.push({d[start], start}); while(!pq.empty()){ auto cur = pq.top(); pq.pop(); if(d[cur.S] != cur.F) continu..

그리디 문제이다. 조를 나누는 문제이므로 K-1의 칸막이를 설치한다고 생각할 수 있다. 직관: 한 조의 차이가 가장 작아야 하므로 일단 가장 차이가 큰 곳에 칸막이를 우선적으로 설치하면 차이가 최대가 될 것 같다. 반례: 가정 결론 도출 코드 #include #include #define F first #define S second using namespace std; int N, K, h[300000], sum; pair dif[300000]; bool devide[300000]; int main(void){ cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); cin >> N >> K; for(int i=0; i> h[i]; for(int i=0; i

stack의 이용한 괄호쌍의 유효성 검사 문제이다. 하지만 이 문제는 값이 존재하여 연산이 추가되었다. 먼저, 괄호가 닫힐 때마다 곱해진 값을 더해주고 갱신하면서 계산하려고 했으나 앞의 값들이 다 날아가는 문제가 생겼다. 다른 방법을 다른 블로그들을 참고하다 괄호가 열릴 때 미리 계산해야 한다는 사실을 깨달았고 이 과정에서 분배법칙을 이용하였다. #include #include #include using namespace std; string str; int temp, ans; stack bracket; char pre; int main(void){ cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); temp = 1; cin >> str; for(auto e..

1. 문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 2. 풀이 아이디어 알고리즘 코드 #include #include #include #define F first #define S second #define IN(Y, X) Y >= 0 && Y = 0 && X < N using namespace std; queue q; int dy[4] = {0, 1, 0, -1}; int dx[4] = {1, 0, -1, 0}..

#include #include #include #include #define F first #define S second #define IN(Y, X) Y >=0 && Y =0 && X < M using namespace std; int N, M, cheese, board[100][100]; bool visit[100][100]; queue q; vector melt; int dy[4] = { 0, 1, 0, -1 }; int dx[4] = { 1, 0, -1, 0 }; void BFS(int y, int x) { visit[y][x] = true; q.push({ y, x }); while (!q.empty()) { pair front = { q.front().F, q.front()..

1. 문제 https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 2. 풀이 아이디어 제한 시간이 2초인 만큼 모든 수를 선형탐색해도 시간이 넉넉하다. 따라서 1부터 N까지 반복문을 다음 수를 만들면 된다. 분해합이 N이 되는 순간 반복문을 멈추고 바로 답을 출력하면 통과 시간을 최대한 빠르게 할 수 있다. 분해합을 구하는 과정은 [자릿수 분해] 알고리즘을 사용한다. 알고리즘 순서 1 ~ N까지 반복문을 돌며 현재의 숫자의..