King of the Jungle Lion

문제링크: 1420번: 학교 가지마! (acmicpc.net) 1420번: 학교 가지마! 첫째 줄에 도시의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 100) 둘째 줄부터 N개의 줄에 도시의 모양이 주어진다. 비어있으면 점('.'), 벽은 '#', 도현이의 위치는 K, 학교의 위치는 H이다. www.acmicpc.net 이 문제는 NxM 크기의 도시에 도현이의 위치와 학교의 위치와 벽의 위치가 주어졌을 때, 도현이가 학교에 갈 수 없게 하려면 최대 몇개의 벽을 세워야 하는지 구하는 문제이다. 최대 개수와 최소 개수를 생각해 보면 최소 개수는 도현이와 학교가 이미 분리된 위치에 있을 때 0, 따로 있을때 학교를 상하좌우로 막은 경우 4 이렇게 최소 0, 최대 4를 가질 수 있다. 이 ..

문제링크: 13547번: 수열과 쿼리 5 (acmicpc.net) 13547번: 수열과 쿼리 5 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, Ai+1, ..., Aj에 존재하는 서로 다른 수의 개수를 출력한다. www.acmicpc.net 이 문제는 길이가 N인 수열에서 (i, j)가 입력인 쿼리가 주어졌을때 i번째 수부터 j번째 수까지 다른 수의 개수를 출력하는 쿼리를 구현하는 문제이다. 이 문제를 풀기 위해서는 mo's 알고리즘에 대해 알고 있어야 한다. mo's 알고리즘은 주어진 쿼리들의 순서를 오프라인 쿼리처럼 특정한 방법으로 배열 한 뒤, 이전의 쿼리의 답을 이용해 가며 다음 쿼리의 답을 구하는 방법이다. 여기서 ..

문제링크:19585번: 전설 (acmicpc.net) 19585번: 전설 Sogang ICPC Team에는 색상 이름과 닉네임의 순서로 이여서 팀명을 지으면 ICPC 리저널에서 수상할 수 있다는 전설이 있다. 색상 이름들과 닉네임들이 주어질 때, Q개의 팀에 대해 다음 리저널에서 수 www.acmicpc.net 이 문제는 트라이를 이용하여 문자열을 탐색해 나가는 문제이다. 특이한 점으로는 color을 뜻하는 문자열 C개, name을 뜻하는 문자열 N개가 주어지고 팀 명이 주어지는데, 팀명이 반드시 color 문자열 + name 문자열 형식으로 이루어 져 있는지 판별해야 한다. C, N은 모두 최대 4000개까지 주어질 수 있고, color, name의 문자열 개수는 최대 1000자 이다. 팀의 개수 Q는..