취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 17841번 문제인 UNIST는 무엇의 약자일까?이다.
문제는 아래 링크를 확인하자.

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

새 문자열을 받을 때마다 기존 "UNIST" 문자열을 만드는 과정에 새 문자열의 접두사(prefix)를 추가해야 한다는 점에 유의하자.

U-, UN-, UNI-, UNIS-, UNIST-, N-, NI-, NIS-, NIST-, I-, IS-, IST-, S-, ST-, T- 형태의(단, -는 뒤에 적절하게 UNIST를 잇지 못하는 다른 글자가 오거나 문자열이 끊어진 것을 의미한다) 경우의 수들을 모두 살펴 점화식을 세우는 것으로 문제를 해결할 수 있다.

코드의 형태가 유사하므로 적절히 복사와 붙여넣기를 활용하면 구현을 빠르게 할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

ll U = 0, N = 0, I = 0, S = 0, T = 0;
ll MOD = 1000000007;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int Q; cin >> Q;
	while (Q--) {
		string s; cin >> s;
		s += "XXXXX";
		if (s[0] == 'U') {
			U++;
			if (s[1] == 'N') {
				N++;
				if (s[2] == 'I') {
					I++;
					if (s[3] == 'S') {
						S++;
						if (s[4] == 'T') {
							T++;
						}
					}
				}
			}
		}
		if (s[0] == 'N') {
			N+=U;
			if (s[1] == 'I') {
				I+=U;
				if (s[2] == 'S') {
					S+=U;
					if (s[3] == 'T') {
						T+=U;
					}
				}
			}
		}
		if (s[0] == 'I') {
			I += N;
			if (s[1] == 'S') {
				S += N;
				if (s[2] == 'T') {
					T += N;
				}
			}
		}
		if (s[0] == 'S') {
			S += I;
			if (s[1] == 'T') {
				T += I;
			}
		}
		if (s[0] == 'T') {
			T += S;
		}

		U %= MOD; N %= MOD; I %= MOD; S %= MOD; T %= MOD;
	}

	cout << T;
}