씅의 기록하는 개발노트

문제 출처

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을 출력합니다.

소스코드

문제풀이

 일반적인 bfs로 풀이 하였다. 큐에 소요시간 정보와 현재 위치를 저장한 구조체를 넣어 문제를 해결했다.

하지만 여기서 다음 파이프의 조건을 판단할때 반대로 생각해야 한다는 것이 매우 중요했다. 이 문제의 핵심 포인트이다!! 

계속 지체되었던 부분인데 현재 위치에서 오른쪽으로 간다고 가정한다면, 다음위치의 파이프는 왼쪽이 뚫려있어야 한다! 

소스코드

문제풀이

상당히 어렵게 푼 문제이다. 단순히 구현하는 문제(시뮬레이션)인데 공유하는 BC가 있을경우 선택을 잘 해야한다.

유저 a와 b의 경로를 2차원 배열에 저장하고 이동이 끝나면 시작위치의 좌표를 재조정한다.

이때 1) 유저 a만 충전하는 경우 2) 유저 b만 충전하는 경우 3) 유저 a,b 모두 충전하는 경우

총 3가지로 나누어 처리하였다.

소스코드

문제풀이

dfs로 완전탐색하여 풀이하였다.

문제의 핵심은 가장 높은곳에서 시작하는 것과 공사를 오직 1번만 진행할 수 있다는 것이다.

input을 받을때 가장 큰 높이를 저장한 뒤 값을 참조하여 탐색한다. 처음에는 좌표를 저장하여 그 좌표에서만 시작하려 했는데 큰 차이는 없을것 같아 높이를 참조하여 시작점을 찾았다.

1. 내리막길인 경우 dfs로 길이를 구해주면 되고

2. 오르막길이고 공사를 진행한 적이 없다면 최소한의 높이를 깎은 뒤 내리막 길이 되면 dfs로 길이를 구해주면 된다. 이때 최대값 k만큼의 높이를 깎는다면 다음 좌표로 이동할 수 없을 수도 있으니 주의하자.

이후 dfs를 통해 등산로 길이의 최대값을 출력해주는 문제이다.

소스코드

최대점과 최소점의 차이를 가장 작게 하기 위해서는 가장 큰값을 빼고 가장 낮은값을 더해주면 된다.

즉, 배열을 먼저 sorting한 다음 덤프하는 수만큼 연산을 하고 sorting을 반복해주면 된다.

소스코드

문제 설명이 좀 어렵게 되있는데 

dfs로 정점의 마지막까지 탐색한 뒤 길이 존재하면 1, 존재하지 않으면 0을 출력해주면 된다.

소스코드

별찍기 문제처럼 접근했다. 

항상 map의 가로, 세로 길이가 홀수인것에서 힌트를 얻을 수 있었다.

가운데를 기준으로 세로로 접으면 대칭되는데 이 값들만 for루프를 통해 더해주면 되는 문제이다.

처음에 많이 헷갈렸는데 그림을 그려가면 규칙을 금방 찾을 수 있었던 문제

소스코드

현미빵(a), 단호박 빵(b)중 더 싼 가격의 빵으로 현재 가지고 있는 돈(c)을 나눠주면 된다.

소스코드