본문 바로가기

Problem Solving/문제풀이

(45)
[BOJ] 1011 Fly me to the Alpha Centauri 문제: https://www.acmicpc.net/problem/1011 그냥 노가다로 규칙 찾는게 증명하는 것보다 빠르다.결국은 수열 길이가 있을때 하나씩 증가/감소/유지되는 수열의 길이가 n이 되는 경우가 있느냐... 찾는 문제인데예를 들어서 수열 길이가 7이라고 하면 1 2 3 4 3 2 1 이런 식으로 이동하는 것이 최대라는 것은 자명하다.그런데 만약에 이렇게 7번의 이동으로 16의 거리를 이동했으면 그 이하의 거리는 모두 이동할 수 있을까? 당연하다.항상 수열에서 가장 큰 원소를 하나 줄이면 그 원소는 절대로 다른 원소와 2 이상 차이가 나지 않게 만들수 있는 것을 너무 간단히 증명할 수 있다.수열 $a_1, a_2, a_3, ... , a_n$ 이 있다고 하자. 만약 $a_k$가 최대 원소라고..
[BOJ] 1918 후위표기식 문제: https://www.acmicpc.net/problem/1918 후위표기식은 스택의 대표주자라 할 만큼 중요한 내용이다.알고리즘은 간단하다. 1. 열린 괄호 -> push2. 닫힌 괄호 -> 열린 괄호가 나올때까지 pop3. 피연산자 -> 그대로 출력4. 연산자 -> 자기보다 우선순위가 낮거나, 열린 괄호가 나오거나, 스택이 빌 때까지 pop 후 push 코드는 이를 그대로 구현했다.4번에 열린 괄호가 나오는 것을 별도로 처리해주지 않은데 주의. 난이도는 1.5/5 정도? 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #include using ..
[BOJ] 1874 스택 수열 문제: https://www.acmicpc.net/problem/1874 굉장히 간단해 보이는 문제와 굉장히 간단한 해법이다.그저 숫자를 스택에 차례대로 넣으면서 지금 빼야 하는 숫자가 top이면 pop해주면 된다.만약에 모든 알고리즘이 끝났는데도 stack이 비지 않았다면 NO. 코드를 좀 더 깔끔하게 짤 수 있을 것 같다. 고민 좀 해 봐야징아마 난이도는 1/5 정도 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #include using namespace std; stack S;vector oper; int main(){ int i=1,j=1,n,a..
[BOJ] 3986 좋은 단어 문제: https://www.acmicpc.net/problem/3986 사실 괄호 문자열 처리하는 문제와 다를 것이 전혀 없습니다. 굳이 스택을 써야 하는지도 모르겠는 문제... 지만 어쨌던 간에 스택 태그가 달려있어서 풀어봤습니다. 코드에서 '_'를 먼저 추가해서 오버플로우를 방지한 영향으로 만족 조건이 S.empty()가 아닌 S.size()==1이 된 것에 주의합시다. 난이도는 1/5. 기초 중의 기초. 12345678910111213141516171819202122232425262728293031323334#include #include #include using namespace std; int solve(){ char str[100005]; stack S; S.push('_'); scanf(..
[BOJ] 2841 외계인의 기타 연주 문제: https://www.acmicpc.net/problem/2841 설명: 항상 가장 높은 플랫만이 연주된다는 점에서 실마리를 찾아볼 수 있다. 어떤 줄 A에 만약 B의 음을 연주해 달라는 쿼리가 들어왔다고 하자. 1. 현재 그 줄에 누르고 있는 손가락이 없는 경우 이 경우에는 당연히 주어진 음에 해당하는 손가락을 누르고 음을 연주하면 된다. 이때 손가락을 한번 누른다. 2. 현재 그 줄에 누르고 있는 가장 높은 손가락이 주어진 음과 같은 경우 손가락을 따로 움직일 필요 없이 그냥 음을 연주하면 된다. 3. 현재 그 줄에 누르고 있는 가장 높은 손가락이 주어진 음보다 낮은 경우 주어진 음에 해당하는 플랫을 누르고, 그 다음 음을 연주하면 된다 4. 현재 그 줄에 누르고 있는 가장 높은 손가락이 주어..