[2023 알고리즘 스터디] 5조 #2주차 - 그리디

FOSCAR 알고리즘 스터디 2주차 5조 블로깅

 

전구와 스위치 - 코드 리뷰 박준석

• 문제 링크

https://www.acmicpc.net/problem/2138

2138번: 전구와 스위치

• 풀이

 

예제에서 000(present) -> 010(target)이 되는 과정은 아래와 같습니다.(최소한의 스위치 누름 횟수)

i번 스위치를 누르면 i-1, i, i+1의 세개의 전구의 상태가 바뀐다.

0번 스위치 누름: 110

1번 스위치 누름: 001

2번 스위치 누름: 010

cnt =3

 

전구의 최대 개수가 십만개 이므로 시간초과를 발생시키지 않도록 for문을 한번만 돌리는 greedy알고리즘을 적용한다.

그렇기 때문에 i위치에서 0부터 i-1까지는 동일해야 다음으로 넘어갈수 있다.  이러한 조건에서 가장 핵심이 첫 번째 전구입니다.

 

#include<iostream>
#include<algorithm>

using namespace std;

int N, result = 987654321, cnt = 0;
string present, target, tmp;

//스위치 누르는 함수
void Push(int idx) {
    // i - 1 전구
    if (idx > 0) {
        if (tmp[idx - 1] == '0') {
            tmp[idx - 1] = '1';
        }
        else {
            tmp[idx - 1] = '0';
        }
    }
    // i 번째 전구
    if (tmp[idx] == '0') {
        tmp[idx] = '1';
    }else {
        tmp[idx] = '0';
    }
    // i + 1 전구
    if (idx < N-1) {
        if (tmp[idx + 1] == '0') {
            tmp[idx + 1] = '1';
        }
        else {
            tmp[idx + 1] = '0';
        } 
    }
}

void solve(int first) {
    //임시적으로 tmp에 저장
    tmp = present;
    cnt = 0;
    // 첫번째코드를 키고 시작하는 경우
    if (first == 0) {
        if (tmp[0] == '0') {
            tmp[0] = '1';
        }else { 
            tmp[0] = '0'; }
        if (tmp[1] == '0') {
            tmp[1] = '1';
        }else {
            tmp[1] = '0';
        }
        cnt++;
    }
    //전구를 하나씩 키는 상태, i는 1부터 시작한다!
    for (int i = 1; i < N; i++) {
        if (tmp[i - 1] != target[i - 1]) {
            Push(i);
            cnt++;
        }
    }
    //만약 전구를 킨 횟수가 result값보다 작을 경우 다시 갱신한다.
    if (tmp == target)
        result = min(result, cnt);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//입력
	cin >> N >> present >> target;
    //첫번째 전구를 키고 시작하는 경우
	solve(0);
    //두번째 전구를 키고 시작하는 경우
	solve(1);
    //result값이 새로 갱신되었으면 바로 출력
	if (result != 987654321)
		cout << result;
	// 불가능한 경우에는 -1을 출력한다. 
	else
		cout << -1;
}

 

 

 

 

 

물병 - 코드 리뷰 박병규

• 문제 링크

https://www.acmicpc.net/problem/1052

1052번: 물병

• 풀이

K개가 넘지 않은 비어있는 물병을 만들고 싶음 -> 같은 양의 물이 들어있는 물병을 두개 고르고 이를 합칠 수 있다

내 생각 2x1 + 2x2 + ... + 2**xk <= N+answer -> answer가 최소가 되게해야함 N, K 는 주어짐 따라서 2의 제곱의 합들이 최소가 되야햠 answer = 2의 k승들의 합 - N

 

example

맨 처음

input 13 2, output 2

1 1 1 1 1 1 1 1 1 1 1 1 1 1

2 2 2 2 2 2 1

4 4 4 1

8 4 1

8 4 (1+3)

8 8

 

13에서 8을 빼고 입력으로 들어온 13에 8을 K에는 1을 빼준다.

이때 K가 1이 되었으므로 남은 N인 5의 값을 2의 거듭제곱 꼴로 만들어 줘야하므로 2의 8-5인 3의 값을 더해준다

 

import math
import sys
# 입력
N, K = map(int,input().split())

# 물병을 구입할 필요가 없을 때
if N <= K :
  print(0)
else :
  input_N = N
  sum = 0 # 2의 거듭제곱의 합으로 나타내줘야함
  tmp = 0 # 남은 N값으로 만들 수 있는 2의 거듭제곱중 가장 큰 값
  while K != 0 :
    if N == 0 : 
      break
    tmp = 2**(int(math.log(N,2)))
    if K == 1 :
      tmp = 2**(int(math.log(N,2))+1)
      if math.log(N,2) == int(math.log(N,2)) :
        tmp = int(2**(math.log(N,2)))

    N = N - tmp
    K = K - 1
    sum = sum + tmp 
    
  print(sum - input_N)

 

 

팥 - 코드 리뷰 이진호

• 문제 링크

https://www.acmicpc.net/problem/1105

1105번: 팔

• 풀이

8의 개수가 가장 적은 숫자의 8의 개수를 구하는 문제입니다.

1.두 숫자 자릿수가 다른 경우 : 값 0

2.두 숫자의 자릿수가 같은 경우 : 앞자리부터 탐색하며 count값을 더해준다. 

import sys
input = sys.stdin.readline
l, r = input().rstrip().split()

def solve():
    if len(l) != len(r):
        print(0)
        return
    count = 0
    for i in range(len(l)):
        if l[i] == r[i]:
            if l[i] == '8':
                count += 1
        else:
            break
    print(count)
    
if __name__ == '__main__':
    solve()

 

 

 

 

PPAP - 코드 리뷰 이승찬 

• 문제 링크

시간 제한 : 1초 (추가 시간 없음)

메모리 제한 : 512MB

알고리즘 분류 : 수학, 그리디 알고리즘, 자료 구조, 문자열, 스택

 

https://www.acmicpc.net/problem/16120

16120번: PPAP

• 풀이

문자열이 ‘P’에서부터 시작 == 입력값을 규칙에 의해 정리하여 PPAP 문자열이면 P만 남아야 함

PPAP = P 로 치환 → stack으로 pop시키며 진행 → pop 4번 + append(’P’) == pop 3번

마지막 남은 stk의 길이가 1이고 그 값이 P이면 PPAP 문자열 / 아니면 NP

 

 

N = input()

stk = []

for i in N:
    stk.append(i)
    if len(stk) >= 4: #기본적으로 stk의 길이가 4 이상이어야 PPAP 조건 만족
        if stk[-1] == 'P' and stk[-2] == 'A' and stk[-3] == 'P' and stk[-4] == 'P':
            stk.pop()
            stk.pop()
            stk.pop()
		# pop 4번 + append(’P’) == pop 3번

if len(stk) == 1 and stk[0] == "P":
    print("PPAP")
else:
    print("NP")

#그리디알고리즘

동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘입니다. 동적 프로그래밍을 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념입니다.

미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법입니다. 이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘이죠.

"매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"