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까지 반복문을 돌며 현재의 숫자의..

1. 문제 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 2. 풀이 아이디어 완전 탐색으로 로프의 모든 조합을 비교하면 부분집합의 개수를 구하는 문제와 같아진다. 이런 경우 2ⁿ의 가지수가 생긴다. 최대 N이 10⁵이므로 완전 탐색을 이용할 경우 무조건 시간 초과가 발생한다. DP를 사용하여 memoization한다고 해도 O(N²)의 시간 복잡도를 가지므로 제한 시간내에 통과할 수 없다. 따라서 더 빠른 풀이를 생각해야 한다. 그러..

1. 문제 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 중복을 허락하여 해당 동전을 만들 수 있는 경우이므로 자연수 분할, 즉 중복 조합문제이다. 2. 풀이 아이디어(시행착오) 동전 n개로 k원을 만들 수 있는경우의 수를 구하는 문제이다. 언뜻 보기엔 일반적인 DFS로 재귀를 이용한 top - down방식으로 풀 생각이 들 수 있다. 예들 들어 1, 2원짜리 동전을 가지고 4원을 만드는 경우 3원(4 - 1원)에 1원을 더한 것과 2원(4 -..

1. 문제 https://www.acmicpc.net/problem/28323 28323번: 불안정한 수열 $N$개의 자연수가 좌우 일렬로 놓여 있다. 왼쪽에서 $i$ ($1 \le i \le N$)번째에 놓여 있는 자연수는 $A_i$다. 여러분은 이 중 몇 개의 자연수를 원하는 만큼 고를 수 있다. 단, 아무 자연수도 고르지 않 www.acmicpc.net 2023년 정보올림피아드 초등부 1번 문제이다. 2. 풀이 문제에서 정의한 불안정안 수열이란 이웃한 두 숫자의 합이 모두 홀수인 수열을 말한다. 자연수의 배열이 주어졌을 때 최대 몇개의 숫자로 불안정한 수열을 만들 수 있는지 구하는 문제이다. 불안정한(이웃한 두 수의 합이 모두 홀수인) 수열을 만들려면 수열을 탐색하며 이웃한 두 수의 합이 짝수가 되..

1. 문제 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 num[i]; lottery(0, 0); cout