이성주

현재를 즐기며 미래를 만드는 개발자, 이성주입니다.

    2022 인하대학교 프로그래밍 경진대회(IUPC) 풀이
A   [BOJ 25205] 경로당펑크 2077
B   [BOJ 25206] 너의 평점은
D   [BOJ 25208] 새벽의 탐정 게임
E   [BOJ 25209] 샤카샤카
F   [BOJ 25210] 정사각형 세기
G   [BOJ 25212] 조각 케이크
H   [BOJ 25214] 크림 파스타
I   [BOJ 25215] 타이핑

1. 문제

$25215$. 타이핑 (2022 인하대학교 프로그래밍 경진대회(IUPC) I번)

백준 25215번 - 타이핑 (https://www.acmicpc.net/problem/25215)

2. 풀이

다음과 같이 dp를 설정할 수 있다.

$dp[i][0]$ $\rightarrow$ 현재 index $i$에서 마름모가 비활성화 상태인 경우, 버튼을 누른 최소 횟수

$1$. 현재 index(i)의 문자가 소문자인 경우 (소문자를 ch, 이 문자의 대문자를 CH라 지칭한다)

$\;$ 1-1. 현재 상태를 비활성화 상태로 종료하는 경우

  • 이전 마름모가 비활성화 상태였던 경우, ch를 누르면, 비활성화 상태를 그대로 유지하면서 해당 문자를 입력할 수 있다. $\rightarrow$ dp[i-1][0]+1

  • 이전 마름모가 활성화 상태였던 경우, ◆를 누르고 ch를 누르면, 해당 문자를 입력하고 비활성화 상태로 바꿀 수 있다. $\rightarrow$ dp[i-1][1]+2

$\;$ 1-2. 현재 상태를 활성화 상태로 종료하는 경우

  • 이전 마름모가 비활성화 상태였던 경우, ch를 누르고 ◆를 누르면, 해당 문자를 입력하고 활성화 상태로 바꿀 수 있다. $\rightarrow$ dp[i-1][0]+2

  • 이전 마름모가 활성화 상태였던 경우, CH를 누르고 ★을 누르면, 해당 문자가 ch로 바뀌고 활성화 상태를 유지할 수 있다. $\rightarrow$ dp[i-1][1]+2

$2$. 현재 index(i)의 문자가 대문자인 경우 (소문자를 ch, 이 문자의 대문자를 CH라 지칭한다)

$\;$ 2-1. 현재 상태를 비활성화 상태로 종료하는 경우

  • 이전 마름모가 비활성화 상태였던 경우, ch를 누르고 ★을 누르면, 해당 문자가 CH로 바뀌고 비활성화 상태를 유지할 수 있다. $\rightarrow$ dp[i-1][0]+2

  • 이전 마름모가 활성화 상태였던 경우, CH를 누르고 ◆을 누르면, 해당 문자를 입력하고 비활성화 상태로 바꿀 수 있다. $\rightarrow$ dp[i-1][1]+2

$\;$ 2-2. 현재 상태를 활성화 상태로 종료하는 경우

  • 이전 마름모가 비활성화 상태였던 경우, ◆를 누르고 CH를 누르면, 활성화 상태로 바뀌고 해당 문자를 입력할 수 있다. $\rightarrow$ dp[i-1][0]+2

  • 이전 마름모가 활성화 상태였던 경우, CH를 한 번 누르면, 활성화 상태를 그대로 유지하면서 해당 문자를 입력할 수 있다. $\rightarrow$ dp[i-1][1]+1

이를 종합하여 다음과 같은 식이 만들어진다.

// if: 현재 index(i)의 문자가 소문자인 경우
dp[i][0] = min(dp[i - 1][0] + 1, dp[i - 1][1] + 2);
dp[i][1] = min(dp[i - 1][0] + 2, dp[i - 1][1] + 2);
// if: 현재 index(i)의 문자가 대문자인 경우
dp[i][0] = min(dp[i - 1][0] + 2, dp[i - 1][1] + 2);
dp[i][1] = min(dp[i - 1][0] + 2, dp[i - 1][1] + 1);

처음은 마름모가 비활성화인 상태에서 시작하기 때문에, 이에 맞춰서 초기값을 잘 설정해주어야 한다.

// if: 첫 글자가 소문자인 경우
dp[0][0] = 1;
dp[0][1] = 2;
// if: 첫 글자가 대문자인 경우
dp[0][0] = 2;
dp[0][1] = 2;

정답은 dp[len - 1][0]와 dp[len - 1][1] 중 작은 값이다.

3. 채점 결과

boj-25215

4. 회고

초기값을 잘못 설정하여 WA를 받았다. 굳이 dp를 사용하지 않고, 그리디 알고리즘으로 풀 수도 있다.

5. 코드

댓글남기기