BOJ(C++) / 백준 15881 : Pen Pineapple Apple Pen

백준 15881 : Pen Pineapple Apple Pen

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

15881번: Pen Pineapple Apple Pen

 

문제

여러 개의 사과, 파인애플, 그리고 펜이 일렬로 세워져 있다. 이 물건들의 순서를 바꾸지 않고 옆에 있는 물건끼리 연결했을 때, 펜-파인애플-애플-펜을 몇 개나 만들 수 있을지 세어보자.

단, 펜, 파인애플, 사과, 펜 순서로 연결된 네 개의 물건만을 펜-파인애플-애플-펜으로 인정하며, 하나의 펜이 두 개의 펜-파인애플-애플-펜에 포함될 수 없다. 또한 펜, 사과, 파인애플, 펜 순서로 연결된 네 개의 물건은 펜-파인애플-애플-펜이 아니다.

 

입력

첫 번째 줄에 물건의 총 개수 n이 주어진다. (1 ≤ n ≤ 1,000,000)

두 번째 줄에 물체의 목록이 길이 n의 문자열로 주어진다. 사과는 A로, 파인애플은 P로, 펜은 p로 대소문자를 구분하여 표기한다.

 

출력

만들 수 있는 펜-파인애플-애플-펜의 최대 개수를 출력한다.

 

코드

//백준 Pen Pineapple Apple Pen_15881
#include <iostream>
#include <string>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	string s;
	cin >> s;

	int count = 0;
	for (int i = 0; i < s.size() - 3; i++) {
		//문자열 자르기
		if (s.substr(i, 4) == "pPAp") {
			count++;
			i += 3;
		}
	}
	cout << count << "\n";

	return 0;
}
//DP 사용?

 

설명

문자열 자르는 함수 substr 함수를 사용하여 문제를 쉽게 구현할 수 있다.

substr

string s = "ApPApPpAPpApPAp";
cout << s.substr(0, 4) << "\n"; // string.substr(자를 위치, 자를 개수)
//출력 = ApPA

pPAp을 찾으면 그다음 위치로 이동할 수 있도록 i+=3을 해주었다.

 

고찰

걸린 시간 : 10분

DP문제라고 해서 풀었는데 DP문제 인가...?? 잘 모르겠다. 그래서 DP로도 풀어보려 했지만 잘 모르겠음..

string 함수 substr 함수를 이미 알고 있어서 문제는 간단하게 구현할 수 있었다. 

 

난이도

Bronze 1