그리디 알고리즘 기초부터 테크닉 익히기1 (중앙값을 0으로 만드는 방법, 구간 축약, 연속 구간 바꾸기, 경우를 나눠 생각하기..)

1. 문제1

 

23758번: 중앙값 제거 (acmicpc.net)

23758번: 중앙값 제거

 

2. 풀이

 

어떤 정수를 2로 나누고 나머지를 버리는 과정을 반복할때, 언제 처음으로 0이 될 수 있을까?

 

1) 결국에 ? > ? > ? > ... ? > 1 > 0 이 되는 과정을 거친다. 즉 반드시 1에서만 0이 될 수 있다. 

 

즉 "중앙값을 2로 나누고 나머지를 버리는 과정"을 계속 수행할때, 반드시 중앙값이 1이 되어야하고,

 

여기서 1번 더 수행하면 0이 될 수 있다.

 

중앙값이 1이 될려면 어떤 조건이 필요할까?

 

2) 해당 중앙값보다 작은 값들은 모두 1이 되어야한다는 것이다.

 

 

처음 중앙값을 2로 나누고 나머지를 버렸을때, 다시 정렬하더라도 처음 중앙값보다 큰 값들은 절대로 중앙값이 될 수 없다.

 

3) 결국에 확인해야할 수들은 0 ~ (n+1)//2-1번 수들이 언제 0이 될 수 있는지 확인해야한다.

 

종합하자면 "중앙값을 2로 나누고 나머지를 버리는 과정"을 계속 반복하다 보면..

 

4) 결국에는 1,1,1,1,1,1,1,?,?,?,?,?...?처럼 중앙값 1 이전의 모든 수들이 1이 되는 결과에 도달해야한다.

 

따라서 0~(n+1)//2-1번 까지 수들을 순회하면서 각각이 2로 나누는 과정을 반복할때 언제 1이 될 수 있는지를 체크하면 된다.

 

또한 각각의 정수 a가 2로 몇번 나눠서 언제 1이 될 수 있는가?는 log2()를 취해서 구할 수 있다.

 

예를 들어 5는 5 > 2 > 1로 2번만에 가능한데, log2(5) = 2.xxxx이므로 int(math.log2(5)) = 2로 구할 수 있다.

 

import math

n = int(input())

A = list(map(int,input().split()))

A.sort()

m = (n+1)//2-1

answer = 0

for i in range(m+1):
    
    answer += int(math.log2(A[i]))

print(answer+1)

 

3. 문제2

 

20365번: 블로그2 (acmicpc.net)

20365번: 블로그2

 

 

4. 풀이1

 

연속된 구간 [L,R]을 잡았을때 같은 색으로 칠할 수 있다.

 

이때 목표로 하는 색깔 열을 몇번만에 만들 수 있는가?

 

연속된 구간 [L,R]을 한번에 같은 색으로 칠할 수 있으므로, 결국 연속된 구간 [L,R]이 같은 색을 목표로 한다면..

 

그거는 1번의 연산으로 칠하면 된다.

 

이 과정을 반복하면 모든 구간을 하나의 색만으로 축약할 수 있는데..

 

즉 BBRBRBBR을 보면 BRBRBR로 만들 수 있다.

 

이렇게 모든 구간이 하나의 색만으로 이루어지게 축약할때, 바깥에 있는 구간부터 안쪽에 있는 구간으로 칠해나가면 최적이 된다.

 

 

 

물론 BRBRBR은 양 끝이 B,R로 서로 다른 색인데.. 서로 다른 색이라면 서로 같은 색이 되도록 한 쪽을 먼저 칠하고

 

BRBRB로 만든 다음 위 과정 처럼 수행하면 된다.

 

 

하나의 색으로 축약하는 과정은 스택을 이용해서 스택의 끝 stack[-1]이 들어오는 문자열 s[i]와 다르다면 스택에 추가해주고

 

같다면 넣어주지 않는다.

 

이렇게 축약이 끝나면, 처음과 끝이 서로 다르다면 처음과 끝이 서로 같을때까지 stack.pop()을 수행

 

이때 색칠은 1번만 하도록 한다.

 

 

BRBRBRRRRRR은 될리가 없겠구나.. 색은 하나씩만 축약시켰으니까?

 

BRBRBR처럼 서로 다르면, 한쪽 R을 지워버리고 BRBRB로 만든 다음 시작 카운트를 1로 시작

 

이 상태에서 전체 길이가 짝수라면 N//2회만에 칠할 수 있을거고

 

홀수라면 N//2+1회만에 칠할 수 있을 것이다.

 

n = int(input())

s = input()

stack = [s[0]]

for i in range(1,n):
    
    if stack[-1] != s[i]:
        
        stack.append(s[i])

answer = 0

if stack[0] != stack[-1]:
    
    stack.pop()
    answer = 1

if len(stack) % 2 == 0:
    
    print(answer + len(stack)//2)

else:
    
    print(answer + len(stack)//2+1)

 

 

5. 풀이2

 

혹은 정말 심플하고 브루트 포스 느낌으로 경우를 나눠서 접근하는 방법이 있는데. (근데 이게 더 깔끔한 접근 같은데..?)

 

1) 전체를 파란색으로 먼저 칠하고, 빨간색의 개수를 센다

 

2) 전체를 빨간색으로 먼저 칠하고, 파란색의 개수를 센다.

 

2가지 경우에서 최솟값이 정답

 

당연히 연속하는 색은 하나의 색으로 칠하는게 유리하니 하나로 센다.

 

 

BBRBRBBR의 경우 BBBBBBBB로 만든 다음 R이 3개 있으니까 4회

 

RRRRRRRR로 만든 다음 B가 3회 있으니까 4회

 

둘의 최솟값은 4이므로 정답은 4가 된다.

 

혹은 BRRBRBRBRRBB를 보면... BBBBBBBBBBBB로 만들고 나서 R이 4개 있으니 5회

 

RRRRRRRRRRRR이 있고 B가 5개 있으니 6회이고.. 최소는 5회이니 정답은 5

 

 

 

연속하는 색을 하나의 색으로 만들고 개수를 세도 되겠지만.. 정말 멋진 방법?이 있는데.. 

 

BBBBBBBBBBBBBBB...로 만든 상태에서 R을 세는 방법은 'RB'의 개수를 세면 된다.

 

왼쪽부터 오른쪽으로 순회하다가 R이 연속해서 나오다가, 처음으로 B가 나오면 1이 카운트 되는거지

 

비슷한 느낌으로

 

RRRRRRRRRRRRRRR...로 만든 상태에서 B를 세는 방법은 'BR'의 개수를 세면 된다.

 

 

왼쪽부터 오른쪽으로 순회하다가 B가 연속해서 나오다가, 처음으로 R이 나오면 1이 카운트 되는거지

 

중요한건 n-1번이 문제인데 n-2번까지 순회하다가 n-2번이 R일때 n-1번이 B이면 반복문에서 카운팅 될거고

 

n-2번까지 순회하다가 n-2번이 R일때, n-1번도 R이면 그것도 R이니까 카운팅 해줘야하는..

 

n = int(input())

s = input()

all_b = 1

for i in range(n-1):
    
    if s[i] == 'R':
        
        if s[i+1] == 'B':
            
            all_b += 1

if s[n-1] == 'R':
    
    all_b += 1

all_r = 1

for i in range(n-1):
    
    if s[i] == 'B':
        
        if s[i+1] == 'R':
            
            all_r += 1

if s[n-1] == 'B':
    
    all_r += 1

if all_b > all_r:
    
    print(all_r)

else:
    
    print(all_b)

 

 

그리디 연습좀 많이해야겠다...