본문 바로가기
X/인알그 스터디

3일차

by 유시은 2020. 9. 15.

2020-09-04
초급 : 2828 사과 담기 게임 (Bronze I)

www.acmicpc.net/problem/2828

 

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)

www.acmicpc.net/problem/17287

 

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)

www.acmicpc.net/problem/16120

 

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")

 

입력을 받아두고 한 글자씩 스택에 넣는다.

 

PPAP는 P로 압축이 가능하다
다른 경우

P를 넣어야 한다면, 최근 들어간 3개를 뽑아 (stack을 사용한 이유이다) PPA 인지 확인하고, 맞다면 P 하나로 압축이 가능하니 P를 하나 넣는다. PPA가 아니라면 다시 집어넣고 P를 하나 더 넣는다.

 

A를 넣어야 한다면 A를 그냥 넣는다. PPAP는 P로 끝나기 때문에 A가 할 수 있는 일이 없다.

 

마지막으로 남은것이 P 하나라면 PPAP 문자열이고, 그 외의 모든 경우엔 PPAP 문자열이 아니다.

 

다음은 예제에 있는 PPPAPAP와 PPAPAPP 를 처리하는 과정이다.

 

 

구현을 P가 들어올 때 마다 3개씩 뽑았다 넣는식으로 했는데 더 좋은 방식이 있을 것이다.

'X > 인알그 스터디' 카테고리의 다른 글

6일차  (0) 2020.09.15
5일차  (0) 2020.09.15
4일차  (0) 2020.09.15
3일차  (0) 2020.09.15
2일차  (0) 2020.09.05
1일차  (0) 2020.09.05

댓글0