Starters 141

👉🏻 Starters 141 | CodeChef

Contest Page | CodeChef

• 이번 글에서는 최근 codechef에서 진행된 "Starters 141" 대회에 대한 문제를 다뤄보겠습니다.

 

Lucky Clover

• N개의 클로버 중 하나는 4잎 클로버이고 나머지는 3잎 클로버일 때, 총 잎의 개수를 계산하는 간단한 사칙 연산 문제입니다.

n = int(input())
print((n-1)*3+4)

 

Nearly Equal

• 문제에서 사용되는 Hamming Distance는 두 문자열에서 서로 다른 문자의 개수로 표현됩니다.
• 문자열 A의 연속된 부분 문자열 중 길이가 M인 것과 문자열 B 사이의 최소 Hamming Distance를 찾는 문제입니다.
• 문자열 A의 부분 문자열마다 Hamming Distance를 구해서 그 중 최솟값을 구하면 끝입니다!

# 두 문자열이 다른 부분을 체크하여 그 수를 합산
def hamming_distance(s1, s2):
    return sum(c1 != c2 for c1, c2 in zip(s1, s2))

# substring마다 hamming distance 구하기
def min_hamming_distance(A, B):
    N, M = len(A), len(B)
    min_distance = M
    
    for i in range(N-M+1):
        substring = A[i:i+M]
        distance = hamming_distance(substring, B)
        # 그 중에서 최솟값 반환
        min_distance = min(min_distance, distance)
    
    return min_distance

def solve():
    N, M = map(int, input().split())
    A = input().strip()
    B = input().strip()
    return min_hamming_distance(A, B)

for _ in range(int(input())):
    print(solve())

 

Redundant Array

• N개의 양의 정수로 이루어진 배열 A의 일부 범위를 선택하여 모든 원소를 동일한 양의 정수 x로 바꾸는 연산을 할 수 있을 때,
• 모든 원소를 동일하게 만들기 위한 최소 비용을 구하는 문제입니다.
• 저는 범위를 1로 고정한 채, 모든 가능한 x값에 대해 배열의 모든 원소를 그 값으로 바꾸는 비용을 계산하고, 그 중 최소 비용을 찾아 반환하여 풀었습니다.
• 자세한 설명은 코드 주석으로 제공하겠습니다.

def solve(N, A):
    # 각 요소의 출현 횟수
    count = [0] * (N + 1)
    for num in A:
        count[num] += 1
    
    # 누적 합 계산
    prefix_sum = [0] * (N + 1)
    for i in range(1, N + 1):
        prefix_sum[i] = prefix_sum[i-1] + count[i]
    
    min_cost = float('inf')
    for x in range(1, N + 1):
    	# x보다 작은 수를 x로 바꾸는 비용 (범위 1 고정)
        cost_smaller = x * prefix_sum[x-1]
        # x보다 큰 수를 x로 바꾸는 비용 (범위 1 고정)
        cost_larger = x * (N - prefix_sum[x])
        # 전체 비용 계산
        total_cost = cost_smaller + cost_larger
        # 최소 비용 갱신
        min_cost = min(min_cost, total_cost)
    return min_cost

for _ in range(int(input())):
    N = int(input())
    A = list(map(int, input().split()))
    print(solve(N, A))