[백준] 3주차(10/1~10/7)

#9012 괄호

분류: 자료구조, 문자열, 스택

#include <iostream>
#include <stack>
using namespace std;

int main() {
	int T;
	cin >> T;
	bool* test = new bool[T];

	for (int i = 0; i < T; ++i) {
		string line;
		cin >> line;

		stack<char> s;
		for (char c : line) {
        	// 여는 괄호'('가 들어온 경우 스택에 push
			if (c == '(') s.push('(');
			else {
            	// 닫는 괄호')'가 들어왔는데 스택이 비어있거나
                // 스택의 맨 위가 여는 괄호'('가 아닌 경우
                // 괄호가 짝을 이루지 않으므로 ')' push
				if (s.empty() || s.top() == ')') s.push(')');
				else  s.pop();
			}
		}
        // 모든 괄호가 짝을 이루는 경우 stack이 비어있어야함
		if (s.empty()) test[i] = true;
		else test[i] = false;
	}

	for (int i = 0; i<T; ++i){
		if (test[i]) printf("YES\n");
		else printf("NO\n");
	}
}

📍 마지막으로 들어온 '('와 처음 들어온 ')'가 짝을 이루어야하므로 스택의 LIFO(Last In First Out) 특징을 이용하였다.

#9095 1, 2, 3 더하기

분류: 다이나믹 프로그래밍

#include <iostream>
using namespace std;

int main() {
	int T, n;
	cin >> T;
	int count[12] = { 0, 1, 2, 4 };
	
	for (int i = 0; i < T; i++) {
		cin >> n;
		for (int i = 4; i <= n; i++) {
			count[i] = count[i - 1] + count[i - 2] + count[i - 3];
		}
		printf("%d\n", count[n]);
	}
}

📍 재귀해야할 것 같은 문제를 볼 때 마다 피보나치를 떠올린다.. 그럼 어떻게든 DP로 풀게 되어있다. 2, 3, 4만 봐도 규칙이 금방 나온다.

4 = 1 + 3 (3을 구하는 식에 1 더하기)
= 2 + 2 (2를 구하는 식에 2 더하기)
= 3 + 1 (1을 구하는 식에 3 더하기)

이런 식으로 입력받은 n까지 구해주면 된다.