Algorithm/Baekjoon

99클럽 코테 스터디 0일차 TIL + [백준 1072]게임 (파이썬 풀이)

도깨비젤리 2024. 10. 28. 14:02

 

 

지정 양식 

제목: 99클럽 코테 스터디 0일차 TIL + 오늘의 학습 키워드

- 오늘의 학습 키워드
- 공부한 내용 본인의 언어로 정리하기
- 오늘의 회고
  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지
  - 어떻게 해결했는지
  - 무엇을 새롭게 알았는지
  - 내일 학습할 것은 무엇인지

필수 해시태그: #99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL

 

 

 

문제링크 

 

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

 

 

 

🤔 문제 설명 및 입출력

 

문제

김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.

이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.

게임 기록은 다음과 같이 생겼다.

  • 게임 횟수 : X
  • 이긴 게임 : Y (Z%)
  • Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z=88이다.

X와 Y가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지 구하는 프로그램을 작성하시오.

입력

각 줄에 정수 X와 Y가 주어진다.

출력

첫째 줄에 형택이가 게임을 최소 몇 판 더 해야하는지 출력한다. 만약 Z가 절대 변하지 않는다면 -1을 출력한다.

제한

  • 1 ≤ X ≤ 1,000,000,000
  • 0 ≤ Y ≤ X



✍ 접근 방법

 

보자마자 이진탐색이다!! 라고 떠올리지는 못했고, 알고리즘 페이지 깔짝깔짝 거리다가 문제 힌트를 봐버린 바람에 (...) 그냥 바로 이진탐색으로 구현해버렸다.

이진탐색으로 solve가 가능한 이유는 문제 조건 중에 나온, 형택이는 무조건 게임을 이긴다, 승률의 소수점을 버린다 <<< 이거 두가지인데, 만약에 이 조건이 없었으면 이진탐색만으로는 해결이 어려웠을 것이다.

그냥 while 문을 돌려서 해결했으나, 개인적인 기벽으로 while문을 별로 안좋아해서 recursive로 다시 구현해봤다.


👨‍💻 소스 코드

  • 파이썬

    - 재귀함수
# 백준 1072
# URL: https://www.acmicpc.net/problem/1072
# 게임횟수 : X
# 이긴 게임 : Y (Z%)
# Z는 승률, 소수점 버린다.
# 최소 몇번의 게임을 해야 승률이 변하는가?
# 1 ≤ X ≤ 1,000,000,000
# 0 ≤ Y ≤ X
# Z가 절대 변하지 않는다면 -1

# constant
MIN_X = 1 
MAX_X = 1000000000

# fn
def get_win_rate(x: int, y: int)->int:
    return (y * 100) // x
x, y = map(int, input().split())

def binary_search(left:int, right:int,win_rate:int,count: int)->int:
    if(left> right): 
        return count
    mid = (left + right) // 2
    new_win_rate = get_win_rate(x + mid, y + mid)
    if new_win_rate > win_rate:
        return binary_search(left, mid-1, win_rate,mid)
    else:
        return binary_search(mid+1, right, win_rate,count)




# main
win_rate = get_win_rate(x, y)


# 승률 계산
initial_win_rate = get_win_rate(x, y)

# 승률은 소숫점 버림이므로 99% 이상이면 더 이상 변하지 않는다
if initial_win_rate >= 99:
    print(-1)
else:
    # 이진탐색 시작
    left, right = MIN_X, MAX_X
    r = binary_search(left, right, initial_win_rate,0)
    print(r)

 


- 단순 loop

# 백준 1072
# URL: https://www.acmicpc.net/problem/1072
# 게임횟수 : X
# 이긴 게임 : Y (Z%)
# Z는 승률, 소수점 버린다.
# 최소 몇번의 게임을 해야 승률이 변하는가?
# 1 ≤ X ≤ 1,000,000,000
# 0 ≤ Y ≤ X
# Z가 절대 변하지 않는다면 -1

# constant
MIN_X = 1 
MAX_X = 1000000000

# fn
def get_win_rate(x: int, y: int)->int:
    return (y * 100) // x


x, y = map(int, input().split())




# main
win_rate = get_win_rate(x, y)


# 승률 계산
initial_win_rate = get_win_rate(x, y)

# 승률은 소숫점 버림이므로 99% 이상이면 더 이상 변하지 않는다
if initial_win_rate >= 99:
    print(-1)
else:
    # 이진탐색 시작
    left, right = MIN_X, MAX_X
    result = 0
     while left <= right:
         mid = (left + right) // 2
         new_win_rate = get_win_rate(x + mid, y + mid)
         if new_win_rate > initial_win_rate:
             result = mid
             right = mid - 1
         else:
             left = mid + 1
     print(result)





🔥 강평

 

- 오늘의 학습 키워드
   * 이진탐색
- 공부한 내용 본인의 언어로 정리하기
   * 완료
- 오늘의 회고
  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지
     * 문제 : 이진탐색, 시도 : 루프와 재귀함수로 해결해보려함
  - 어떻게 해결했는지
    * 루프와 재귀함수로
  - 무엇을 새롭게 알았는지
   * 파이썬 간만에 하니까 적응이 안되는구나...
  - 내일 학습할 것은 무엇인지
   * -

 

 

 

 

여담

 

PS 능력이 요즘 떨어진다고 생각해서 다시 알고리즘 공부를 시작하고 생각했는데, 나 혼자서 PS 한다고 깝죽거렸다가 몇일 못하고 뻗을거 같다는 생각이 들어 굉장히 고민하고 있었습니다.

 

그런데, 우연한 기회로 항해99 라는 곧에서 하루에 알고 한 문제씩 풀 수 있도록 시스템을 마련해뒀더라고요?

1일1문이면 크게 부담도 없을뿐더러, 꾸준함을 기르는데 도움이 될 거 같아 신청해서 오늘부터 시작했습니다.

 

근데.... 얘들이 TIL 쓰는걸 굉장히 강조하는 바람에... 방치되고 있던 블로그를 다시 살리고 말았네요.. TIL 안쓰면 레벨 안올려준다고 하니까 울면서 글 쓰고 있습니다.

 

왠지 양산형 기술블로그 만드는 느낌이 들어서 ( 큰 의미 없이 글 갯수만 올리기 위한 기술블로그 ) 좀 기분이 꼬림한데, 그래도 이왕 하기로 한거, 월급루팡 제대로 하면서 내실있게 적어보겠습니다.

저작자표시