[프로그래머스] 카운트 다운 (DP, 다트)

2023. 8. 10. 22:08·Coding Test/programmers
728x90

https://school.programmers.co.kr/learn/courses/30/lessons/131129

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

분석

1. 가장 먼저 0점을 만든 선수가 승리
2. "싱글" 또는 "불"을 더 많이 던진 선수가 승리
3. 선공인 선수가 승리

최선의 경우 던질 다트 수와 그 때의 "싱글" 또는 "불"을 맞춘 횟수(합)

1. 1-60점 dp 채우기

2. 23부터 target 까지 1-60점 빼고 새로 맞추는 점수와 비교

 

2023.05.19 - [백준/동적계획법] - 동전 교환 (DP)

 

동전 교환 (DP)

분석 더보기

karla.tistory.com

 

풀이

import sys
def solution(target):

    n = max(61, target+1)
	
    # d[i] : [i 점수를 맞출 때 맞춘 최소 수, 싱글이거나 불 횟수]
    d = [[target, 0] for _ in range(n)]  # 조합수, 싱글, 불 개수

    d[50] = [1, 1] # 불 

    for i in range(1, 21): # 1~60 (싱글, 더블, 트리플)
        if 1<=i<= 20:
            d[i]=[1, 1]
        if d[i*2] == [target, 0]:
            d[i*2] = [1, 0]
        if d[i*3] == [target, 0]:
            d[i*3] = [1, 0] 

    for i in range(23, n):
        single = [] # 싱글, 불

        for j in range(1, 61):
            if d[i-j][0] + d[j][0] <= d[i][0]: # 새로 맞추는거랑 원래 개수랑 비교
                d[i][0] = d[i-j][0] + d[j][0] # 최솟값으로 설정
                single.append([d[i-j][0] + d[j][0], d[i-j][1] + d[j][1]])

        single.sort(key=lambda x: [x[0], -x[1]])

        if len(single) > 0:
            d[i] = single[0]

    return d[target]
728x90
저작자표시 비영리 변경금지 (새창열림)
'Coding Test/programmers' 카테고리의 다른 글
  • [프로그래머스] N으로 표현
  • [프로그래머스] 스타수열
  • [프로그래머스] 모두 0으로 만들기 (그래프 DFS)
  • [프로그래머스] 영어 끝말잇기
Karla Ko
Karla Ko
𝘾𝙤𝙣𝙩𝙞𝙣𝙪𝙤𝙪𝙨𝙡𝙮 𝙄𝙢𝙥𝙧𝙤𝙫𝙞𝙣𝙜, 𝘾𝙤𝙣𝙨𝙩𝙖𝙣𝙩𝙡𝙮 𝘿𝙚𝙫𝙚𝙡𝙤𝙥𝙞𝙣𝙜 𝙔𝙚𝙨!
    250x250
  • Karla Ko
    karlaLog
    Karla Ko
  • 전체
    오늘
    어제
    • Total (467)
      • Spring (19)
      • JPA (4)
      • Cloud & Architecture (15)
        • Kubernetes (5)
        • Docker (3)
        • MSA (2)
        • GCP (1)
        • AWS (4)
      • Devops (1)
      • Message Queue (4)
        • Kafka (2)
        • RabbitMQ (2)
      • Git (4)
      • DB (4)
      • Java (9)
      • Python (4)
      • CS (11)
        • OS (8)
        • Network (2)
        • Algorithm (1)
      • Coding Test (392)
        • programmers (156)
        • Graph (43)
        • DP (37)
        • Search (31)
        • Tree (13)
        • Data Structure (26)
        • Combination (12)
        • Implement (18)
        • Geedy (23)
        • Sort (7)
        • Math (21)
        • geometry (2)
  • 블로그 메뉴

    • 홈
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    LIS
    재귀
    DP
    파이썬
    구현
    플로이드워셜
    스택
    BFS
    조합
    최소신장트리
    DFS
    Algorithm
    그래프
    월간코드챌린지
    자료구조
    힙
    덱
    백준
    구간합
    트리
    그리디
    동적계획법
    다익스트라
    프로그래머스
    이분탐색
    알고리즘
    최대공약수
    최단거리
    큐
    정렬
  • hELLO· Designed By정상우.v4.10.3
Karla Ko
[프로그래머스] 카운트 다운 (DP, 다트)
상단으로

티스토리툴바