🚲 백준 17609. 회문

문제

회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.

여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다.

입력

입력의 첫 줄에는 주어지는 문자열의 개수를 나타내는 정수 T(1 ≤ T ≤ 30)가 주어진다. 다음 줄부터 T개의 줄에 걸쳐 한 줄에 하나의 문자열이 입력으로 주어진다. 주어지는 문자열의 길이는 3 이상 100,000 이하이고, 영문 알파벳 소문자로만 이루어져 있다.

출력

각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.

예제 입력 1

7
abba
summuus
xabba
xabbay
comcom
comwwmoc
comwwtmoc

예제 출력 1

0
1
1
2
2
0
1

풀이

• 팰린드롬 문제
• 회문: 0, 유사회문: 1, 그 외: 2
• 유사회문은 문자를 하나 제거했을 때 회문이 성립되는 것을 말한다.

코드

T = int(input())
arr = []
str = []
for i in range(T):
    arr.append(input())
for i in range(T):
    for j in range(len(arr[i])//2): # 문자열을 절반으로 나누어 탐색
        if(arr[i][j] != arr[i][len(arr[i])-j-1]): # 회문이 아닌 경우
            
            for n in range (len(arr[i])) : # 유사회문인 경우
                str = arr[i][0:n] + arr[i][n+1:] # 원본 문자열에서 문자를 하나씩 제거해본다.
                
                for m in range(len(str[0])//2): # 문자열을 절반으로 나누어 탐색
                    if(str[0][m] != str[0][len(str[0])-m-1]): # 회문이 아닌 경우
                        print('2')
                        break
                    else:
                        print('1')
                        break
        else: # 그 외는 모두 회문
            print('0')
            break

---

🚲 백준 9084. 동전

문제

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다.

동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 동전의 가지 수 N(1 ≤ N ≤ 20)이 주어지고 두 번째 줄에는 N가지 동전의 각 금액이 오름차순으로 정렬되어 주어진다. 각 금액은 정수로서 1원부터 10000원까지 있을 수 있으며 공백으로 구분된다. 세 번째 줄에는 주어진 N가지 동전으로 만들어야 할 금액 M(1 ≤ M ≤ 10000)이 주어진다.

편의를 위해 방법의 수는 231 - 1 보다 작고, 같은 동전이 여러 번 주어지는 경우는 없다.

출력

각 테스트 케이스에 대해 입력으로 주어지는 N가지 동전으로 금액 M을 만드는 모든 방법의 수를 한 줄에 하나씩 출력한다.

예제 입력 1

3\
2\
1 2\
1000\
3\
1 5 10\
100\
2\
5 7\
22

예제 출력 1

501\
121\
1

알고리즘 분류

• 다이나믹 프로그래밍
• 배낭 문제

풀이

• 동전: 1원, 5원, 10원, 50원, 100원, 500원
• 테스트 케이스의 개수 = T
• 동전의 가지 수 = N
• 동전으로 만들어야 할 금액 = M

코드

t = int(input()) # 테스트 케이스 개수

for _ in range(t): # 테스트 케이스 개수만큼 반복
    n = int(input()) # 동전의 가지 수
    c = list(map(int, input().split())) # 동전 종류
    m = int(input()) # 금액
    
    arr = [0 for i in range(m+1)]
    arr[0] = 1 # 각 동전에 따른 
    
    for i in c: # 동전의 종류만큼 반복
        for j in range(1,m+1): # 금액 내에서 탐색한다.
            if j >= i:
                arr[j] += arr[j-i] # 동전의 액수만큼 이전인 인덱스 값을 더해준다. (그 사이를 건너뛴다.)
        print('arr: ', arr)
    print(arr[m])