2020-09-04
초급 : 2828 사과 담기 게임 (Bronze I)
2828번: 사과 담기 게임
상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M<n) 플레이어는="" 게임을="" 하는="" 중에="" 바구니를="" �<="" p=""> </n)>
www.acmicpc.net
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <string>
using namespace std;
int N, M, J;
int lp, rp, res;
int apple[20];
int main() {
cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
cin >> N >> M >> J;
lp = 1;
rp = M;
for (int i = 0; i < J; ++i) {
cin >> apple[i];
}
for (int i = 0; i < J; ++i) {
if (lp > apple[i]) {
res += (lp - apple[i]);
rp -= (lp - apple[i]);
lp -= (lp - apple[i]);
}
else if (rp < apple[i]) {
res += (apple[i] - rp);
lp += (apple[i] - rp);
rp += (apple[i] - rp);
}
}
cout << res;
return 0;
}
최적의 선택은 가만히 있을 수 있다면 가만히 있고, 움직여야 한다면 최소한만 움직이는 것이다.
중급 : 17287 The Deeper, The Better (Silver III)
17287번: The Deeper, The Better
대괄호, 중괄호, 소괄호와 0부터 9까지의 숫자로 이루어진 문자열 S가 주어진다. 문자열 S는 올바른 괄호 문자열에 숫자를 끼워 넣은 형태이고, 두 숫자가 서로 붙어있는 경우는 없다. 올바른 괄
www.acmicpc.net
from sys import stdin
def input(): return stdin.readline().rstrip()
s, p, r = input(), 0, 0
for c in s:
if c=="(": p += 1
if c=="{": p += 2
if c=="[": p += 3
if c==")": p -= 1
if c=="}": p -= 2
if c=="]": p -= 3
if c>='0' and c<='9': r = max(r, p)
print(r)
숫자가 받는 점수는 결국 숫자가 나오기 이전 열리고 아직 닫히지 않은 괄호들의 점수의 합이다.
고급 : 16120 PPAP (Gold IV)
16120번: PPAP
첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다.
www.acmicpc.net
from sys import stdin
from collections import deque
def input(): return stdin.readline().rstrip()
s = input()
p = deque()
for c in s:
if c == "P":
if len(p) >= 3:
ppa = p.pop() + p.pop() + p.pop()
if ppa == "APP":
p.append("P")
continue
else:
for i in ppa:
p.append(i)
p.append("P")
else:
p.append("A")
print("PPAP" if len(p) == 1 and p.pop()=="P" else "NP")
입력을 받아두고 한 글자씩 스택에 넣는다.
P를 넣어야 한다면, 최근 들어간 3개를 뽑아 (stack을 사용한 이유이다) PPA 인지 확인하고, 맞다면 P 하나로 압축이 가능하니 P를 하나 넣는다. PPA가 아니라면 다시 집어넣고 P를 하나 더 넣는다.
A를 넣어야 한다면 A를 그냥 넣는다. PPAP는 P로 끝나기 때문에 A가 할 수 있는 일이 없다.
마지막으로 남은것이 P 하나라면 PPAP 문자열이고, 그 외의 모든 경우엔 PPAP 문자열이 아니다.
다음은 예제에 있는 PPPAPAP와 PPAPAPP 를 처리하는 과정이다.
구현을 P가 들어올 때 마다 3개씩 뽑았다 넣는식으로 했는데 더 좋은 방식이 있을 것이다.
댓글