β 10162 μ μλ μΈμ§ β
T=int(input())
a=T//300
flag=0
for i in range(a,-1,-1):
after_A=T-i*300
b=after_A//60
for j in range(b,-1,-1):
after_B=after_A-j*60
if after_B%10==0:
flag+=1
k=after_B//10
print(i,j,k)
break
if flag==1:
break
if flag==0:print(-1)
π greedy κ΄μ λΆμ
: κ°λ³ μν©) A / B / C λ²νΌμ λλ₯΄λ μν©
: μ’ ν© μν©) A / B / C λ²νΌμ μ¬λ¬ λ² λλ¬ T timeμ λ± λ§κ² μ리νκΈ°
β μ΅μ μ μ’ ν© μν©μ μ΅μ μ κ°λ³ μν©μ λͺ¨μμΌλ‘ λ§λ€ μ μκ³ , κ°λ³ μν©μ μ΅μ greedy μ루μ μ Aλ²νΌμ μ°μ μ μΌλ‘ → Bλ²νΌ → Cλ²νΌμ λλ₯Έλ€. (μκ° ν¨μ¨μ μν΄ κ΅¬νλ©΄ λ°λ‘ breakλ¬Έ)
π λ¨Όμ 300μ΄λ‘ λλ μ§λ€λ©΄, κ·Έλ€μ 100μ΄λ‘ λλ μ§λ μ§ νμΈνκ³ , λ§μ§λ§μΌλ‘ 10μΌλ‘ λλ μ§λ μ§ μ°¨λ‘λλ‘ νμΈ.
→ greedyν λ¬Έμ μ΄λ―λ‘, 300μ΄λ‘ λλ λͺ«μ΄ ν° κ²λΆν° 0κΉμ§ κ±°κΎΈλ‘ μ°¨λ‘λλ‘ νμΈνλ€κ° λ΅μ΄ λμ€λ©΄ print()νκ³ λ°λ‘ break!
β 3578 Holes β
h=int(input())
if h==0:print(1)
elif h==1:print(0)
else:
if h%2==0:print('8'*(h//2))
else:print('4'+'8'*(h//2))
π greedy κ΄μ λΆμ (κ°λ³ μν©μ΄ λΆκΈ°λ¬ΈμΌλ‘ λλμ΄μ§)
: κ°λ³ μν©) holeμ λ§λ€κΈ° μν΄ 0/4/6/9/8μ€ ν κ° μ«μλ₯Ό λλ₯΄λ μν©
: μ’ ν© μν©) μ«μλ₯Ό μ¬λ¬ λ² λλ¬ λ§λ μ«μκ° μ΅μκ°μΌλ‘ λμ€κ³ / λλ₯΄λ κ°μ hκ° μ΅μκ°μ΄ λκ²λ λ§λ€κΈ°
β μ΅μ μ μ’ ν© μν©μ μ΅μ μ κ°λ³ μν©μ λͺ¨μμΌλ‘ λ§λ€ μ μκ³
→ κ°λ³ μν©μ μ΅μ greedy μ루μ : λλ₯Ό λ 8μ μ°μ μ μΌλ‘ λλ₯΄λ, hκ° νμμΌ κ²½μ° 4λ₯Ό λ¨Όμ λλ₯΄κ³ μ΄ν 8 λλ₯΄κΈ° (hκ° 0κ³Ό 1λ§ μμΈ)
π ꡬλ©μ΄ μκΈ°λ μ«μ 0,4,6,9,8μ μ‘°ν©μΌλ‘λ§ λ§λ€μ΄μΌ νκ³ , 맨 μμ 0μ΄ λ λ² μ°μ μ¬ μ μλ€.
π μ΅μκ°μΌλ‘ λ§λ€μ΄μΌ νλ―λ‘ μλ¦Ώμκ° μ΅μμ¬μΌ νλ€. λ°λΌμ 8λ‘ μ΅λν ꡬμ±μ΄ λμ΄μΌ ν¨ (greedy)
β νμκ°μμ holeμ λ§λ€μ΄μΌ νλ€λ©΄ 8μ μ΅λν μ±μ°κ³ , λ§μ§λ§ κ°μ 1κ°λ κ°μ₯ μ΅μκ°μΈ 4 - μ¦ 48888~ ννμ¬μΌ νλ€.
β‘ μ§μκ°μμ holeμ λ§λ€μ΄μΌ νλ€λ©΄ 8λ‘λ§ κ΅¬μ±λμ΄μΌ νλ€.
β’β£ holeμ΄ μλ€λ©΄ 1, holeμ΄ 1κ° μλ€λ©΄ 1
β 2720 μΈνμ μ¬μ₯ λν β
for _ in range(int(input())):
C=int(input())
print(C//25,(C%25)//10,((C%25)%10)//5,C%5)
π greedy κ΄μ λΆμ
: κ°λ³ μν©) μΏΌν° / λ€μ / λμΌ / νλ μ€ ν ννμ μ’ λ₯λ₯Ό μ νν΄ λμ κ±°μ¬λ¬ μ£Όλ μν©
: μ’ ν© μν©) μ£Όμ΄μ§ λμ μ¬λ¬ ννλ‘ κ±°μ¬λ¬ μ£Όλ μν© / λλ₯΄λ κ°μ hκ° μ΅μκ°μ΄ λκ²λ λ§λ€κΈ°
β μ΅μ μ μ’ ν© μν©μ μ΅μ μ κ°λ³ μν©μ λͺ¨μμΌλ‘ λ§λ€ μ μκ³
→ κ°λ³ μν©μ μ΅μ greedy μ루μ : μΏΌν° - λ€μ - λμΌ - νλ μμΌλ‘ λ¨Όμ μ’ λ₯λ₯Ό μ ν
π λμ μ κ°μλ₯Ό μ΅μν ν΄μΌνλ―λ‘ μΏΌν° - λ€μ - λμΌ - νλ μμΌλ‘ greedyνκ² μ μΌ ν° κΈμ‘λΆν° κ°μλ₯Ό countνλ€
β 14720 μ°μ μΆμ β
import sys
input=sys.stdin.readline
N=int(input())
l=list(map(int,input().split()))
t=0
direction=0
for i in l:
if direction==0 and i==0:
t+=1
direction+=1
elif direction==1 and i==1:
t+=1
direction+=1
elif direction==2 and i==2:
t+=1
direction-=2
print(t)
π greedy κ΄μ λΆμ
: κ°λ³ μν©) κ° μ°μ κ°κ²μμ λΈκΈ° / μ΄μ½ / λ°λλ / x(μ λ§μ¬) μ€ ν κ°λ₯Ό μ νν΄ λ§μλ μν©
: μ’ ν© μν©) λͺ¨λ μ°μ κ°κ²μμ κ°κ°μ μ°μ λ₯Ό λ€μνκ² μ νν΄ λ§μλ μν© / λ§μλ μ°μ κ°μκ° μ΅λκ°μ΄ λκ²λ λ§λ€κΈ°
β μ΅μ μ μ’ ν© μν©μ μ΅μ μ κ°λ³ μν©μ λͺ¨μμΌλ‘ λ§λ€ μ μκ³
→ κ°λ³ μν©μ μ΅μ greedy μ루μ : κ° κ°κ²μμλ μ°μ λ₯Ό 1λ²λ§ λ§μ€ μ μμΌλ―λ‘ λ§μλ κ·μΉμ΄ μ±λ¦½νλ€λ©΄ 'λ°λ‘' κ·Έ κ°κ²μμ λ§μ¬. (Xλ₯Ό μ ννμ§ μκ³ λ§μλ μ루μ )
π λ§μ€ μ μλ€λ©΄ λ°λ‘ λ§μλ, greedy μ ν! direction λ°©ν₯ λ³μλ₯Ό μ¬μ©ν΄, direction λ³μμ λ§λ κ°μ΄λΌλ©΄ λ°λ‘ λ§μκ²λ μ½λ 짬
π λ°©ν₯λ³μλ₯Ό μ¬μ©ν μ½λ κΈ°μ΅νμ!
β 17931 Greedily Increasing Subsequence β
import sys
input=sys.stdin.readline
N=int(input())
A=list(map(int,input().split()))
ans=[A[0]]
l=1
cur=A[0]
for ai in A[1:]:
if ai>cur:
ans.append(ai)
l+=1
cur = ai
print(l)
print(*ans)
π greedy κ΄μ λΆμ
: κ°λ³ μν©) Subsequenceλ₯Ό λ§λ€κΈ° μν΄ νμ¬μ μ«μλ₯Ό subsequenceμ λ£μ μ§ μ λ£μ μ§ κ²°μ νλ μν©
: μ’ ν© μν©) Greedily Increasing Subsequenceλ₯Ό λ§λλ μν©
β μ΅μ μ μ’ ν© μν©μ μ΅μ μ κ°λ³ μν©μ λͺ¨μμΌλ‘ λ§λ€ μ μκ³
→ κ°λ³ μν©μ μ΅μ greedy μ루μ : νμ¬ Cur κ°λ³΄λ€ ν° κ°μ΄λ©΄ subsequenceμ λ£κΈ°λ₯Ό μ ν
β 5585 κ±°μ€λ¦λ β
n=0
money=1000-int(input())
for x in [500,100,50,10,5,1]:
n+=(money//x)
money%=x
print(n)
π greedyνκ² ν° νν λ¨μλΆν° λ¨Όμ μΉ΄μ΄νΈ. κ·ΈλμΌ μ΅μ’ νν μ§ν κ°μ μ΅μν κ°λ₯
β 4796 μΊ ν β
import sys
input=sys.stdin.readline
i=0
while 1:
i+=1
L,P,V=map(int,input().split())
if (L,P,V)==(0,0,0):break
print(f'Case {i}: {(V//P)*L+min(L,V%P)}')
π greedy κ΄μ λΆμ
: κ°λ³ μν©) κ° μΌμ λ³λ‘ μΊ νμ κ° μ§, λ§ μ§ κ²°μ
: μ’ ν© μν©) μΊ νμ₯μ κ°λ λ μ μ΄ λνκΈ°
β μ΅μ μ μ’ ν© μν©μ μ΅μ μ κ°λ³ μν©μ λͺ¨μμΌλ‘ λ§λ€ μ μκ³
→ κ°λ³ μν©μ μ΅μ greedy μ루μ : μΊ νμ₯ κ°λ μ΅λ μΌμ(μ΅λν κ° PμΌ μ€ 1μΌλΆν° LμΌκΉμ§ μ κ° λ€μ, κ·Έ λ€μ PμΌμμλ 1μΌμμ LμΌκΉμ§ κ° μ μκ² νλ€. μ£Όμ΄μ§ PμΌμμ μ΅λ LμΌμ κ½κ½ μ±μ°λ κ² κ° PμΌμμμ greedyν κ²°μ . νλ°μ κ°λ€λ©΄ λ€μ PμΌμμμ LμΌκ³Ό κ²Ήμ³ μΊ νμ λͺ» κ° μ μμΌλ―λ‘ 1μΌλΆν° λͺ°μ κ°κ² ν΄μΌ μ΅λ LμΌμ κ½κ½ μ±μ + λλ¨Έμ§λ LμΌκ³Ό λΉκ΅ν΄μ minκ° μΆκ°)
β 2864 5μ 6μ μ°¨μ΄ β
A,B=input().split()
a1,b1=A.replace('6','5'),B.replace('6','5')
a2,b2=A.replace('5','6'),B.replace('5','6')
print(int(a1)+int(b1),int(a2)+int(b2))
π greedy κ΄μ λΆμ
: κ°λ³ μν©) 5μ 6μ λ§λλ©΄ κ°κ° 5λ‘ λ°κΏ μ§, 6μΌλ‘ λ°κΏ μ§ κ²°μ
: μ’ ν© μν©) λ μμ ν©
β μ΅μ μ μ’ ν© μν©μ μ΅μ μ κ°λ³ μν©μ λͺ¨μμΌλ‘ λ§λ€ μ μκ³
→ κ°λ³ μν©μ μ΅μ greedy μ루μ : μ΅μκ°μ λͺ¨λ 6μ 5λ‘, μ΅λκ°μ λͺ¨λ 5λ₯Ό 6μΌλ‘ (replace()λ‘ νλ²μ)
β 30019 κ°μμ€ μμ½ μμ€ν β
π νμ¬ μμ μμ λΉμ₯ κ°μκ° λ¨Όμ μ΄λ¦¬λ κ°μλ₯Ό μ ννλ―λ‘ greedyμ μ κ·Ό. cur listμ κ° κ°μμ€μ λ μκ°μ update. sκ° μλ°ν μμΌλ‘ μ£Όμ΄μ§λ―λ‘ κ° line μ§ννλ©΄μ νμ¬μ eμ λΉκ΅ν΄ YES / NO μΆλ ₯
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
cur = [0 for _ in range(N)]
for _ in range(M):
k,s,e=map(int,input().split())
if s >= cur[k-1]:
print('YES')
cur[k-1]= e
else:
print('NO')
'BOJ > π₯' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
β Math & Geometry Upper-Beginner II - 19 Solvedβ (0) | 2023.04.06 |
---|---|
β Math Beginner IV - 22 Solvedβ (0) | 2023.01.16 |
β Math Beginner III - 30 Solvedβ (1) | 2022.11.18 |
β Sorting Beginner I - 8 Solvedβ (0) | 2022.11.14 |
β Implementation&Simulation Upper-Beginner I - 25 Solvedβ (0) | 2022.11.03 |
λκΈ