씅의 기록하는 개발노트

문제 출처

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

문제 설명

스택 성질에 대해 이해가 필요한 문제입니다. 처음에 고민하다가 입력받은 숫자가 나올때까지 push하다가 입력받은 숫자가 나오면 pop해주면 쉽게 풀 수 있는 문제입니다. idea가 필요했던 문제!

소스 코드

//
//  main.cpp
//  BOJ_1874
//
//  Created by sw on 17/12/2019.
//  Copyright © 2019 seungwoo. All rights reserved.
//

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin>>n;
    int num[n];
    vector<char> ret;
    stack<int> st;
    
    for (int i=0; i<n; i++) cin>>num[i];
    
    int idx=0;
    for (int i=1; i<=n; i++) {
        st.push(i);
        ret.push_back('+');

        while (!st.empty() && st.top() == num[idx]) {
            idx++;
            st.pop();
            ret.push_back('-');
        }
    }
    
    if (!st.empty()) cout<<"NO"<<"\n";
    else for (auto c : ret) cout<<c<<"\n";
    
    return 0;
}

[문제 출처]

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

1부터 N까지 자연수중 길이가 M인 순열을 출력하는 문제입니다.

[순열 ?]

 순열은 주어진 수열에서 순서에 따라 결과가 달라지는 방식입니다. 즉 순서가 존재하는 열인 것이죠.

c++기준 next_permutation / prev_permutation과 같은 STL함수를 통해 쉽게 구현할 수 있습니다. 

[문제풀이]

 완전 탐색을 통해 문제를 풀이합니다. DFS방식으로 basecase조건 충족시 출력을 하고 함수에서 나오는 방법입니다. 이때 visit배열로 방문여부를 체크하여 중복 값이 사용되는 것, 다시말해 같은 수를 여러번 고르는 경우를 방지하면 됩니다.

[소스코드]

#include <iostream>
#include <vector>
using namespace std;
int n,m;
vector<int> v;
bool visit[9];
void solve(int cnt) {
	if (cnt == m) {
		for (int i=0; i<v.size(); i++) cout<<v[i]<<" ";
		cout<<"\n";
		return;
	}
	
	for (int i=1; i<=n; i++) {
		if (visit[i]) continue;
		visit[i] = 1;
		v.push_back(i);
		solve(cnt+1);
		visit[i] = 0;
		v.pop_back();
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	solve(0);
	return 0;	
}

문제출처

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

문제풀이

 삼성 역량테스트 기출문제 입니다.

문제에서 원하는 답은 보드를 상,하,좌,우 방향으로 기울였을때 빨간구슬만을 구멍으로 빼낼 수 있는 최소횟수입니다. 이때, 파란구슬은 빠지면 안되고 보드는 총 10번 이하로 움직여야 합니다. 출력은 목적을 달성하는 최소횟수이고 파란구슬이 빠지거나 보드를 10번이상 움직였다면 -1을 출력하면 됩니다.

문제이해를 위해 예제를 따라해보면 더 쉽게 이해하실 수 있습니다.

예제를 따라하면 처음에 왼쪽으로 움직이고 다음번에 오른쪽으로 움직인경우 구슬의 위치가 같은 것을 알 수 있습니다. 또한 같은 방향으로 반복적으로 움직여도 구슬의 위치에는 영향을 받지 않는다는 것을 알 수 있습니다.

즉, 같은방향 혹은 이전방향과 반대방향으로 움직일 경우는 제외해도 됩니다. (구슬의 위치가 같다면 이러한 경우에 해당됩니다.)

문제풀이 과정은 다음과 같습니다.

1.  빨간공을 움직입니다.

2. 파란공을 움직입니다.

3. 파란공이 구멍으로 빠진경우 잘못된 경우이므로 제외합니다.

4. 빨간공과 파란공의 위치가 중복된 경우 공의 위치를 재조정합니다.

    만약 빨간공이 3칸, 파란공이 2칸이동했다면 빨간공의 위치를 이동방향 기준으로 1번 뒤로 되돌립니다.

    예를 들어 # . . R B #일때 왼쪽으로 기울인다면 공의 위치가 겹치기 때문에 # (R,B) . . . # 와 같은 상태입니다.

    이 경우 빨간공이 2칸, 파란공이 3칸움직였기 때문에 파란공을 오른쪽으로 1번 되돌려야 정상적인 좌표를 가지게 됩니다.

5. 이과정을 반복하면서 빨간공만 빠지고 움직인 횟수가 10번이내라면 횟수를 출력하고 이외의 경우에는 -1을 출력합니다.

소스코드