하용권

https://www.acmicpc.net/problem/9095

mem[n] = mem[n-1] + mem[n-2] + mem[n-3]

을 이용(1,2,3만 이용 해서 가능)

#include <iostream>
using namespace std;
int main(){
	int mem[11] = {0};
	int T,n;
	mem[1] = 1; mem[2] = 2; mem[3] = 4;
	cin >> T;
	
	for(int i = 0; i < T; i++){
		cin >> n;
		for(int j = 4; j <= n; j++){
        	mem[j] = mem[j-1] + mem[j-2] + mem[j-3];
        }
		cout << mem[n] << endl;
	}
	
}

bfs로도 풀 수 있을 거 같아서, bfs로도 한 번 풀어봤습니다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int bfs(int n) {
	bool visit[1000001];
	int idx=n;
    int count = 0;
    queue<int> q;
    q.push(n);
 
    while(1) {
        int size = q.size();
 
        for(int i=0; i<size; i++) {
            idx = q.front();
            q.pop();
            if(idx == 1)
                return count;        
            if(visit[idx-1] == 0) {
                q.push(idx-1);
                visit[idx-1] = 1;
            }
            if(idx%2 == 0 && visit[idx/2] == 0) {
                q.push(idx/2);
                visit[idx/2] = 1;
            }
            if(idx%3 == 0 && visit[idx/3] == 0) {
                q.push(idx/3);    
                visit[idx/3] = 1;
            }
        }
		
        count++;
    }
}
int main(){
	int n;
	cin >> n;
	
	cout << bfs(n);
	return 0;
}

https://www.acmicpc.net/problem/3986

스택으로 짜면 쉬울 거 같아 짜봤습니다.

#include <iostream>
#include <stack>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	int N,ret = 0;
	cin >> N;
	
	for(int i= 0; i< N; i++){
		string str;
		stack<char> st;
		cin >> str;
	
		for(int j = 0; j < str.length(); j++){
			
			if(!st.empty()&&st.top() == str[j])st.pop();
			else st.push(str[j]);
		
		}
		if(st.empty()) ret+=1;
	}
	cout << ret;
}