[그리디] 1105 팔, 12904 A와 B

9. 1105 팔

9.1. 유형파악

1. 그리디
2. 그리디 유형은 정렬과 함께 출제될 확률이 높다.
3. 문제 유형을 한 번에 파악하기 어려울 경우 그리디를 의심해볼 것
4. 종종 DP, Graph 알고리즘과 함께 출제된다.
5. 그리디는 반드시 최적의 해를 구할 수 있는 지 의심해봐야한다.

9.2. 해결과정

1. 주어진 l, r 사이에서 8을 가장 적게 포함하는 횟수를 구하는 문제이다.
2. 수의 범위가 20억이므로, 순차탐색으로 해결할 수 없다.
3. 8의 최소 개수만 세면 된다는 것에 초점을 맞춰 풀어야한다.
4. l과 r의 첫번째 자리수부터 비교하되 일치하면서 8이라면 개수를 카운트하고, 다르다면 stop한다.
   • 만약 자리수의 값이 다르다면, (8이 아닌 다른값으로 설정해버리면 개수가 0이된다.)
   • 바로 stop하는 이유는, 이미 앞 자리수가 다르므로 뒷자리는 다양한 값(0~9)을 가질 수 있다.

9.3. 소스코드

l, r = map(str, input().split())

answer = 0

if len(l)!=len(r):
    print(0)
    exit(0)

for i in range(len(l)):
    if l[i]==r[i]:
        if l[i]=='8':
            answer += 1
    else:
        break
print(answer)

10. 12904 A와 B

10.1. 유형파악

1. 문자열, 그리디, 구현
2. 그리디 + 정렬 유형이 많다는 걸 인지할 것
3. 문제 유형 파악이 어려울 시 그리디 고려할 것
4. DP, Graph와 함께 나오는 경우도 있음을 인지할 것
5. 그리디로 풀이할 시 반드시 최적의 해를 구할 수 있는지 고려할 것

10.2. 해결과정

1. 이 문제는 S -> T로 가는 경우의 수를 계산하면 어렵다.
2. S가 T가 될 수 있는 지 확인하는 걸 뒤집어서 접근하면 쉽다.
3. T가 S가 될 수 있는 지 규칙 1, 규칙 2를 뒤집어서 적용해서 해결했다.

10.3. 소스코드

s = input()
t = input()
s, t = list(s), list(t)

for i in range(len(t)-1, -1, -1):
    if t==s:
        print(1)
        exit(0)
    elif t[i]=='A':
        t.pop()
    else:
        t.pop()
        t = t[::-1]
print(0)