[백준] 11585번 속타는 저녁 메뉴

2024. 12. 1. 20:43·백준 문제/KMP

문제: 11585번 속타는 저녁 메뉴

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>

using namespace std;

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

	int n; // 문자열 s 와 p 의 길이
	cin >> n;
	string P = ""; // 패턴
	string S = "";

	for (int i = 0; i < n; i++) {
		char c;
		cin >> c;
		P += c; // 연결, 공백 문자 없애기
	}
	for (int i = 0; i < n; i++) {
		char c;
		cin >> c;
		S += c;
	}

	// 입력된 문자열이 IWANTMEAT 이었을 때 얘를 제곱하면 IWANTMEATIWANTMEAT 이 된다.
	// 근데 위 문자열 전체에 KMP 를 수행하면 문제가 발생한다.
	// 그냥 하면 IWANTMEAT 를 두 번 확인할 수 있기 때문에 마지막 문자를 빼줘야한다..
	string doubleS = S + S;
	doubleS = doubleS.substr(0, doubleS.size() - 1);

	// KMP 사용하여 패턴이 몇 번 등장하는지 계산
	// pi 배열 먼저 구하기(패턴의 실패 함수)
	vector<int> pi(n + 1); // LPS 배열을 오른쪽으로 한 칸 민 것과 같으므로 n+1 만큼 크기 잡아주기
	int i = 1;
	int j = 0;
	while (i < n) {
		if (P[i] == P[j]) {
			i++;
			j++;
			pi[i] = j;
		}
		else if (j == 0) {
			i++;
			pi[i] = j;
		}
		else {
			j = pi[j]; // 저장해둔 곳으로 점프
		}
	}
	// 이제 doubleS 랑 P 비교 해서 패턴 개수 찾기
	int cnt = 0;
	i = 0;
	j = 0;
	
	while (i < doubleS.size()) {
		if (doubleS[i] == P[j]) {
			i++;
			j++;

			// 패턴 찾았으면 cnt 값 +1 해주고 점프
			if (j == n) {
				cnt++;
				j = pi[j];
			}
		}
		else if (j == 0) {
			i++;
		}
		else {
			j = pi[j];
		}
	}

	// 기약 분수 계산
	// 두 수의 최대공배수를 구해준 다음
	// 그 값으로 각 수를 나눠주고 출력..
	int gcd = 1;
	for (int i = 1; i <= n; i++) {
		if ((cnt % i == 0) && (n % i == 0)) {
			gcd = i;
		}
	}
	cout << (cnt / gcd) << "/" << (n / gcd) << "\n";


	return 0;
}

 

이 문제의 핵심은 주어진 문자열이 원판에 있기 때문에 원형 문자열이다. 즉 이 문제를 해결하기 위해서는 입력 받은 문자열을 제곱해 준 후 맨 마지막 글자만 떼준 다음 KMP 를 돌리면 되는 것이었다.

 

 

 

참고자료:

문제)

https://chatgpt.com/share/674c4b7d-8fc8-8003-aec5-21f3ee12a201

 

ChatGPT - 문자열 회전 처리

Shared via ChatGPT

chatgpt.com

[BOJ] 백준 11585번 속타는 저녁 메뉴 (Java)

 

[BOJ] 백준 11585번 속타는 저녁 메뉴 (Java)

#11585 속타는 저녁 메뉴 난이도 : 플레 5 유형 : 문자열 / KMP 11585번: 속타는 저녁 메뉴 수원이와 친구들은 저녁 메뉴를 잘 선택하지 못한다. 배가 고픈 수원이가 보다 못해 메뉴를 정하곤 하는데 이

loosie.tistory.com

백준 11585 속타는 저녁 메뉴 Kotlin (kmp)

 

백준 11585 속타는 저녁 메뉴 Kotlin (kmp)

문제 출처 : https://www.acmicpc.net/problem/11585 11585번: 속타는 저녁 메뉴 수원이와 친구들은 저녁 메뉴를 잘 선택하지 못한다. 배가 고픈 수원이가 보다 못해 메뉴를 정하곤 하는데 이마저도 반대에 부

ongveloper.tistory.com

 

최소공배수)

[1934] 최소공배수 - C++ : 네이버 블로그

 

[1934] 최소공배수 - C++

테스트 케이스의 개수 T를 입력받아 두번째 줄부터 T줄에 걸쳐서 정수 A, B의 쌍이 주어진다. A와 B...

blog.naver.com

 

'백준 문제/KMP' 카테고리의 다른 글
  • [백준] 4354번 문자열 제곱
  • [백준] 1305번 광고
  • [백준] 1786번 찾기
dubu0721
dubu0721
dubu0721 님의 블로그 입니다.
  • dubu0721
    dubu0721 님의 블로그
    dubu0721
  • 전체
    오늘
    어제
    • 분류 전체보기 (351) N
      • 프로그래밍언어론 정리 (5)
      • 컴퓨터네트워크 정리 (5)
      • 알고리즘&자료구조 공부 (64)
        • it 취업을 위한 알고리즘 문제풀이 입문 강의 (60)
        • 학교 알고리즘 수업 (3)
        • 실전프로젝트I (0)
      • 백준 문제 (204) N
        • 이분탐색 (7)
        • 투포인트 (10)
        • 그래프 (11)
        • 그리디 (24)
        • DP (25)
        • BFS (21) N
        • MST (7)
        • KMP (4)
        • Dijkstra (3)
        • Disjoints Set (4)
        • Bellman-Ford (2)
        • 시뮬레이션 (3)
        • 백트래킹 (15)
        • 위상정렬 (5)
        • 자료구조 (25)
        • 기하학 (1)
        • 정렬 (11)
        • 구현 (8)
        • 재귀 (8)
        • 수학 (8)
        • 트리 (1)
      • 유니티 공부 (11)
        • 레트로의 유니티 게임 프로그래밍 에센스 (11)
        • 유니티 스터디 자료 (0)
        • C# 공부 (0)
      • 유니티 프로젝트 (48)
        • 케이크게임 (13)
        • 점토게임 (35)
      • 언리얼 공부 (10)
        • 이득우의 언리얼 프로그래밍 (10)
      • 진로 (1)
      • 논문 읽기 (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    유니티 프로젝트
    티스토리챌린지
    그리디
    골드메탈
    레트로의 유니티 프로그래밍
    투포인터
    이벤트 트리거
    백트래킹
    dp
    스택
    언리얼
    C#
    유니티 공부 정리
    맵
    해시
    BFS
    자료구조
    백준
    큐
    수학
    우선순위큐
    이득우
    이분탐색
    유니티
    그래프
    오블완
    재귀
    정렬
    바킹독
    시뮬레이션
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
dubu0721
[백준] 11585번 속타는 저녁 메뉴
상단으로

티스토리툴바