λ°˜μ‘ν˜•

πŸ“¦ Changgo 316

[BOJ][C++] λ°±μ€€ 11000번: κ°•μ˜μ‹€ λ°°μ • (Gold V)

https://www.acmicpc.net/problem/11000 λ¬Έμ œμˆ˜κ°•μ‹ μ²­μ˜ λ§ˆμŠ€ν„° κΉ€μ’…ν˜œ μ„ μƒλ‹˜μ—κ²Œ μƒˆλ‘œμš΄ κ³Όμ œκ°€ μ£Όμ–΄μ‘Œλ‹€.κΉ€μ’…ν˜œ μ„ μƒλ‹˜ν•œν…ŒλŠ” Si에 μ‹œμž‘ν•΄μ„œ Ti에 λλ‚˜λŠ” N개의 μˆ˜μ—…μ΄ μ£Όμ–΄μ§€λŠ”λ°, μ΅œμ†Œμ˜ κ°•μ˜μ‹€μ„ μ‚¬μš©ν•΄μ„œ λͺ¨λ“  μˆ˜μ—…μ„ κ°€λŠ₯ν•˜κ²Œ ν•΄μ•Ό ν•œλ‹€.참고둜, μˆ˜μ—…μ΄ λλ‚œ 직후에 λ‹€μŒ μˆ˜μ—…μ„ μ‹œμž‘ν•  수 μžˆλ‹€. (즉, Ti≤ Sj일 경우 i μˆ˜μ—…κ³Ό j μˆ˜μ—…μ€ 같이 듀을 수 μžˆλ‹€.)μˆ˜κ°•μ‹ μ²­ λŒ€μΆ©ν•œ 게 찔리면, μ„ μƒλ‹˜μ„ λ„μ™€λ“œλ¦¬μž!μž…λ ₯첫 번째 쀄에 N이 μ£Όμ–΄μ§„λ‹€. (1 ≤ N ≤ 200,000)이후 N개의 쀄에 Si, Tiκ°€ μ£Όμ–΄μ§„λ‹€. (0 ≤ Si좜λ ₯κ°•μ˜μ‹€μ˜ 개수λ₯Ό 좜λ ₯ν•˜λΌ. 풀이// 풀이 : https://whkakrkr.tistory.com#include using namespace std;..

[BOJ][C++] λ°±μ€€ 21314번: λ―Όκ²Έ 수 (Silver I)

https://www.acmicpc.net/problem/21314 λ¬Έμ œλ―Όκ²Έμ΄λŠ” 둜마 숫자λ₯Ό 보고 ꡉμž₯히 ν₯λ―Έλ‘­λ‹€κ³  μƒκ°ν–ˆλ‹€. κ·Έλž˜μ„œ λ―Όκ²Έμ΄λŠ” μƒˆλ‘œμš΄ 수 체계인 λ―Όκ²Έ 수λ₯Ό μ°½μ‘°ν–ˆλ‹€.λ―Όκ²Έ μˆ«μžλŠ” 0 μ΄μƒμ˜ μ •μˆ˜N에 λŒ€ν•΄ 10Nλ˜λŠ” 5 × 10N꼴의 μ‹­μ§„μˆ˜λ₯Ό λŒ€λ¬ΈμžMκ³ΌK둜 이루어진 λ¬Έμžμ—΄λ‘œ ν‘œκΈ°ν•œλ‹€. 10N꼴의 μ‹­μ§„μˆ˜λŠ”N+ 1개의M으둜, 5 × 10N꼴의 μ‹­μ§„μˆ˜λŠ”N개의M뒀에 1개의Kλ₯Ό 이어뢙인 λ¬Έμžμ—΄λ‘œ λ‚˜νƒ€λ‚Έλ‹€. 즉, μ•„λž˜ ν‘œμ²˜λŸΌ λ‚˜νƒ€λ‚Ό 수 μžˆλ‹€.λ―Όκ²Έ μˆ˜λŠ” ν•œ 개 μ΄μƒμ˜ λ―Όκ²Έ 숫자λ₯Ό 이어뢙여 λ§Œλ“ λ‹€. 예λ₯Ό λ“€μ–΄, λ―Όκ²Έ 수MKKMMKλŠ”MK,K,MMK의 μ„Έ λ―Όκ²Έ 숫자λ₯Ό 이어뢙여 λ§Œλ“€ 수 μžˆλ‹€.λ―Όκ²Έ 수λ₯Ό μ‹­μ§„μˆ˜λ‘œ λ³€ν™˜ν•  λ•ŒλŠ”, 1개 μ΄μƒμ˜ λ―Όκ²Έ 숫자둜 λ¬Έμžμ—΄μ„ λΆ„λ¦¬ν•œ λ’€, 각각의 λ―Όκ²Έ 숫자λ₯Ό μ‹­μ§„μˆ˜λ‘œ λ³€ν™˜ν•΄μ„œ 순..

[BOJ][C++] λ°±μ€€ 19598번: μ΅œμ†Œ νšŒμ˜μ‹€ 개수 (Gold V)

https://www.acmicpc.net/problem/19598 λ¬Έμ œμ„œμ€€μ΄λŠ” μ•„λΉ λ‘œλΆ€ν„° N개의 회의λ₯Ό λͺ¨λ‘ μ§„ν–‰ν•  수 μžˆλŠ” μ΅œμ†Œ νšŒμ˜μ‹€ 개수λ₯Ό κ΅¬ν•˜λΌλŠ” λ―Έμ…˜μ„ λ°›μ•˜λ‹€. 각 νšŒμ˜λŠ” μ‹œμž‘ μ‹œκ°„κ³Ό λλ‚˜λŠ” μ‹œκ°„μ΄ μ£Όμ–΄μ§€κ³  ν•œ νšŒμ˜μ‹€μ—μ„œ λ™μ‹œμ— 두 개 μ΄μƒμ˜ νšŒμ˜κ°€ 진행될 수 μ—†λ‹€. λ‹¨, νšŒμ˜λŠ” ν•œλ²ˆ μ‹œμž‘λ˜λ©΄ μ€‘간에 쀑단될 수 μ—†μœΌλ©° ν•œ νšŒμ˜κ°€ λλ‚˜λŠ” 것과 λ™μ‹œμ— λ‹€μŒ νšŒμ˜κ°€ μ‹œμž‘λ  수 μžˆλ‹€. 회의의 μ‹œμž‘ μ‹œκ°„μ€ λλ‚˜λŠ” μ‹œκ°„λ³΄λ‹€ 항상 μž‘λ‹€. N이 λ„ˆλ¬΄ μ»€μ„œ κ΄΄λ‘œμ›Œ ν•˜λŠ” 우리 μ„œμ€€μ΄λ₯Ό λ„μ™€μ£Όμž.μž…λ ₯첫째 쀄에 λ°°μ—΄μ˜ 크기 N(1 ≤ N ≤ 100,000)이 μ£Όμ–΄μ§„λ‹€. λ‘˜μ§Έ 쀄뢀터 N+1 μ€„κΉŒμ§€ κ³΅λ°±μ„ 사이에 두고 회의의 μ‹œμž‘μ‹œκ°„κ³Ό λλ‚˜λŠ” μ‹œκ°„μ΄ μ£Όμ–΄μ§„λ‹€. μ‹œμž‘ μ‹œκ°„κ³Ό λλ‚˜λŠ” μ‹œκ°„μ€ 231−1보닀 μž‘κ±°λ‚˜ 같은 μžμ—°..

[BOJ][C++] λ°±μ€€ 13164번: 행볡 μœ μΉ˜μ› (Gold V)

https://www.acmicpc.net/problem/13164 λ¬Έμ œν–‰λ³΅ μœ μΉ˜μ› 원μž₯인 νƒœμ–‘μ΄λŠ” μ–΄λŠ λ‚  Nλͺ…μ˜ 원생듀을 ν‚€ μˆœμ„œλŒ€λ‘œ 일렬둜 쀄 μ„Έμš°κ³ , 총 K개의 쑰둜 λ‚˜λˆ„λ €κ³  ν•œλ‹€. 각 μ‘°μ—λŠ” 원생이 적어도 ν•œ λͺ… μžˆμ–΄μ•Ό ν•˜λ©°, 같은 쑰에 μ†ν•œ 원생듀은 μ„œλ‘œ 인접해 μžˆμ–΄μ•Ό ν•œλ‹€. μ‘°λ³„λ‘œ μΈμ›μˆ˜κ°€ 같을 ν•„μš”λŠ” μ—†λ‹€.μ΄λ ‡κ²Œ λ‚˜λ‰˜μ–΄μ§„ 쑰듀은 각자 단체 ν‹°μ…”μΈ λ₯Ό λ§žμΆ”λ €κ³  ν•œλ‹€. μ‘°λ§ˆλ‹€ ν‹°μ…”μΈ λ₯Ό λ§žμΆ”λŠ” λΉ„μš©μ€ μ‘°μ—μ„œ κ°€μž₯ ν‚€κ°€ 큰 원생과 κ°€μž₯ ν‚€κ°€ μž‘μ€ μ›μƒμ˜ ν‚€ 차이만큼 λ“ λ‹€. μ΅œλŒ€ν•œ λΉ„μš©μ„ 아끼고 μ‹Άμ–΄ ν•˜λŠ” νƒœμ–‘μ΄λŠ” K개의 쑰에 λŒ€ν•΄ ν‹°μ…”μΈ  λ§Œλ“œλŠ” λΉ„μš©μ˜ 합을 μ΅œμ†Œλ‘œ ν•˜κ³  μ‹Άμ–΄ν•œλ‹€. νƒœμ–‘μ΄λ₯Ό 도와 μ΅œμ†Œμ˜ λΉ„μš©μ„ κ΅¬ν•˜μž.μž…λ ₯μž…λ ₯의 첫 μ€„μ—λŠ” μœ μΉ˜μ›μ— μžˆλŠ” μ›μƒμ˜ 수λ₯Ό λ‚˜νƒ€λ‚΄λŠ” μžμ—°μˆ˜ N(1 ≤ N ≤ 3..

[BOJ] λ°±μ€€ 11047번: 동전 0

https://www.acmicpc.net/problem/11047 11047번: 동전 0첫째 쀄에 Nκ³Ό Kκ°€ μ£Όμ–΄μ§„λ‹€. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) λ‘˜μ§Έ 쀄뢀터 N개의 쀄에 λ™μ „μ˜ κ°€μΉ˜ Aiκ°€ μ˜€λ¦„μ°¨μˆœμœΌλ‘œ μ£Όμ–΄μ§„λ‹€. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 κ²½μš°μ— AiλŠ” Ai-1의 배수)www.acmicpc.net λ¬Έμ œμ€€κ·œκ°€ κ°€μ§€κ³  μžˆλŠ” 동전은 총 Nμ’…λ₯˜μ΄κ³ , 각각의 동전을 맀우 많이 κ°€μ§€κ³  μžˆλ‹€.동전을 적절히 μ‚¬μš©ν•΄μ„œ κ·Έ κ°€μΉ˜μ˜ 합을 K둜 λ§Œλ“€λ €κ³  ν•œλ‹€. μ΄λ•Œ ν•„μš”ν•œ 동전 개수의 μ΅œμ†Ÿκ°’μ„ κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.μž…λ ₯첫째 쀄에 Nκ³Ό Kκ°€ μ£Όμ–΄μ§„λ‹€. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)λ‘˜μ§Έ 쀄뢀터 N개의 쀄에 λ™μ „μ˜ κ°€μΉ˜..

[BOJ][C++] λ°±μ€€ 20365번: λΈ”λ‘œκ·Έ2 (Silver III)

https://www.acmicpc.net/problem/20365 λ¬Έμ œneighbor λΈ”λ‘œκ·Έλ₯Ό μš΄μ˜ν•˜λŠ” μΌμš°λŠ” 맀일 μ•„μΉ¨ ν’€κ³  싢은 문제λ₯Ό 미리 정해놓고 κΈ€μ„ μ˜¬λ¦°λ‹€. 그리고 λ§€μΌ λ°€ κ°κ°μ˜ λ¬Έμ œμ— λŒ€ν•˜μ—¬, ν•΄κ²°ν•œ 경우 νŒŒλž€μƒ‰, ν•΄κ²°ν•˜μ§€ λͺ»ν•œ 경우 λΉ¨κ°„μƒ‰μœΌλ‘œ μΉ ν•œλ‹€. μΌμš°λŠ” κ° 문제λ₯Ό μΉ ν•  λ•Œ μ•„λž˜μ™€ 같은 과정을 ν•œ 번의 μž‘μ—…μœΌλ‘œ μˆ˜ν–‰ν•œλ‹€.μž…λ ₯첫째 쀄에 색을 μΉ ν•΄μ•Ό ν•˜λŠ” 문제의 수N(1 ≤N≤ 500,000)이 μ£Όμ–΄μ§„λ‹€.λ‘˜μ§Έ 쀄에N개의 λ¬Έμžκ°€ κ³΅λ°± 없이 μˆœμ„œλŒ€λ‘œ μ£Όμ–΄μ§„λ‹€. 각 λ¬ΈμžλŠ”i번째 문제λ₯Ό μ–΄λ–€ μƒ‰μœΌλ‘œ μΉ ν•΄μ•Ό ν•˜λŠ”μ§€λ₯Ό μ˜λ―Έν•˜λ©°,R은 빨간색,BλŠ” νŒŒλž€μƒ‰μ„ λ‚˜νƒ€λ‚Έλ‹€. κ·Έ 외에 λ‹€λ₯Έ λ¬ΈμžλŠ” μ£Όμ–΄μ§€μ§€ μ•ŠλŠ”λ‹€.좜λ ₯첫째 쀄에 μΌμš°κ°€ μ£Όμ–΄μ§„ λͺ¨λ“  문제λ₯Ό μ›ν•˜λŠ” μƒ‰μœΌλ‘œ μΉ ν•  λ•ŒκΉŒμ§€ ν•„μš”ν•œ μž‘μ—… 횟수의 μ΅œμ†Ÿκ°’μ„ ..

[BOJ][C++] λ°±μ€€ 1931번: νšŒμ˜μ‹€ λ°°μ •

https://www.acmicpc.net/problem/1931 1931번: νšŒμ˜μ‹€ λ°°μ •(1,4), (5,7), (8,11), (12,14) λ₯Ό μ΄μš©ν•  수 μžˆλ‹€.www.acmicpc.net λ¬Έμ œν•œ 개의 νšŒμ˜μ‹€μ΄ μžˆλŠ”λ° 이λ₯Ό μ‚¬μš©ν•˜κ³ μž ν•˜λŠ” N개의 νšŒμ˜μ— λŒ€ν•˜μ—¬ νšŒμ˜μ‹€ μ‚¬μš©ν‘œλ₯Ό λ§Œλ“€λ €κ³  ν•œλ‹€. 각 회의 I에 λŒ€ν•΄ μ‹œμž‘μ‹œκ°„κ³Ό λλ‚˜λŠ” μ‹œκ°„μ΄ μ£Όμ–΄μ Έ 있고, 각 νšŒμ˜κ°€ κ²ΉμΉ˜μ§€ μ•Šκ²Œ ν•˜λ©΄μ„œ νšŒμ˜μ‹€μ„ μ‚¬μš©ν•  수 μžˆλŠ” 회의의 μ΅œλŒ€ 개수λ₯Ό μ°Ύμ•„λ³΄μž. 단, νšŒμ˜λŠ” ν•œλ²ˆ μ‹œμž‘ν•˜λ©΄ 쀑간에 쀑단될 수 μ—†μœΌλ©° ν•œ νšŒμ˜κ°€ λλ‚˜λŠ” 것과 λ™μ‹œμ— λ‹€μŒ νšŒμ˜κ°€ μ‹œμž‘λ  수 μžˆλ‹€. 회의의 μ‹œμž‘μ‹œκ°„κ³Ό λλ‚˜λŠ” μ‹œκ°„μ΄ 같을 μˆ˜λ„ μžˆλ‹€. 이 κ²½μš°μ—λŠ” μ‹œμž‘ν•˜μžλ§ˆμž λλ‚˜λŠ” κ²ƒμœΌλ‘œ μƒκ°ν•˜λ©΄ λœλ‹€.μž…λ ₯첫째 쀄에 회의의 수 N(1 ≤ N ≤ 100,000..

[BOJ][C++] λ°±μ€€ 20115번: μ—λ„ˆμ§€ λ“œλ§ν¬ (Silver III)

https://www.acmicpc.net/problem/20115 λ¬Έμ œνŽ˜μΈμ€ μ—λ„ˆμ§€ λ“œλ§ν¬λ₯Ό μ’‹μ•„ν•˜λŠ” νšŒμ‚¬μ›μ΄λ‹€. μ—λ„ˆμ§€ λ“œλ§ν¬λŠ” 카페인, μ•„λ₯΄κΈ°λ‹Œ, νƒ€μš°λ¦°, λ‚˜μ΄μ•„μ‹  λ“±μ˜ 성뢄이 λ“€μ–΄μžˆμ–΄ ν”Όλ‘œ νšŒλ³΅μ— 도움을 μ£ΌλŠ” μ—λ„ˆμ§€ 보좩 μŒλ£Œμˆ˜μ΄λ‹€.야근을 마치고 ν•œλ°€μ€‘μ— ν‡΄κ·Όν•˜λ‹ˆ 벌써 μƒˆλ²½ 1μ‹œ. ν•˜μ§€λ§Œ 주말은 아직 λ©€μ—ˆκ³ , λ‹€μŒ 날에도 μ •μ‹œμ— μΆœκ·Όν•΄μ•Ό ν•˜λŠ” νŽ˜μΈμ€ μ˜€λŠ˜λ„ μ—λ„ˆμ§€ λ“œλ§ν¬λ₯Ό μ°ΎλŠ”λ‹€.λ°˜λ³΅λ˜λŠ” 야근에 μ§€μΉœ λ‚˜λ¨Έμ§€, ν‰μ†Œλ³΄λ‹€ 더 λ§Žμ€ μ—λ„ˆμ§€μ™€ ν”Όλ‘œ 회볡이 ν•„μš”ν–ˆλ˜ νŽ˜μΈμ€ 집에 있던 μ—λ„ˆμ§€ λ“œλ§ν¬λ“€μ„ ν•œ 데 ν•©μ³μ„œ, ν•˜λ‚˜μ˜ μ—λ„ˆμ§€ λ“œλ§ν¬λ‘œ λ§Œλ“€μ–΄ ν•œλ²ˆμ— λ§ˆμ‹œλ € ν•œλ‹€.페인이 μ—λ„ˆμ§€ λ“œλ§ν¬λ“€μ„ ν•©μΉ˜λŠ” 과정은 λ‹€μŒκ³Ό κ°™λ‹€.예λ₯Ό λ“€μ–΄, 두 μ—λ„ˆμ§€ λ“œλ§ν¬a, bκ°€ 있고, 양이 각각xa, xb라 ν•  λ•Œ, λ‹€μŒ λ‘˜ 쀑..

[BOJ][C++] λ°±μ€€ 11508번: 2+1 세일 (Silver IV)

https://www.acmicpc.net/problem/11508 λ¬Έμ œKSG νŽΈμ˜μ μ—μ„œλŠ” 과일우유, λ“œλ§ν‚Ήμš”κ΅¬λ₯΄νŠΈ λ“±μ˜ μœ μ œν’ˆμ„ '2+1 세일'ν•˜λŠ” 행사λ₯Ό ν•˜κ³  μžˆμŠ΅λ‹ˆλ‹€. KSG νŽΈμ˜μ μ—μ„œ μœ μ œν’ˆ 3개λ₯Ό ν•œ λ²ˆμ— μ‚°λ‹€λ©΄ κ·Έμ€‘μ—μ„œ κ°€μž₯ μ‹Ό 것은 무료둜 μ§€λΆˆν•˜κ³  λ‚˜λ¨Έμ§€ 두 개의 μ œν’ˆ κ°€κ²©λ§Œ μ§€λΆˆν•˜λ©΄ λ©λ‹ˆλ‹€. ν•œ λ²ˆμ— 3개의 μœ μ œν’ˆμ„ 사지 μ•ŠλŠ”λ‹€λ©΄ 할인 없이 μ •κ°€λ₯Ό μ§€λΆˆν•΄μ•Ό ν•©λ‹ˆλ‹€.예λ₯Ό λ“€μ–΄, 7개의 μœ μ œν’ˆμ΄ μžˆμ–΄μ„œ 각 μ œν’ˆμ˜ 가격이 10, 9, 4, 2, 6, 4, 3이고 μž¬ν˜„μ΄κ°€ (10, 3, 2), (4, 6, 4), (9)둜 총 3λ²ˆμ— κ±Έμ³μ„œ 물건을 μ‚°λ‹€λ©΄ 첫 번째 κΎΈλŸ¬λ―Έμ—μ„œλŠ” 13원을, 두 번째 κΎΈλŸ¬λ―Έμ—μ„œλŠ” 10원을, μ„Έ 번째 κΎΈλŸ¬λ―Έμ—μ„œλŠ” 9원을 μ§€λΆˆν•΄μ•Ό ν•©λ‹ˆλ‹€.μž¬ν˜„μ΄λŠ” KSG νŽΈμ˜μ μ—μ„œ μΉœκ΅¬λ“€κ³Ό ..

[BOJ][C++] λ°±μ€€ 1758번: μ•Œλ°”μƒ κ°•ν˜Έ (Silver IV)

https://www.acmicpc.net/problem/1758 λ¬Έμ œμŠ€νƒ€λ°•μŠ€λŠ” μ†λ‹˜μ„ μž…μž₯μ‹œν‚¬ λ•Œ λ…νŠΉν•œ λ°©λ²•μœΌλ‘œ μž…μž₯μ‹œν‚¨λ‹€.μŠ€νƒ€λ°•μŠ€μ—μ„œλŠ” μ†λ‹˜μ„ 8μ‹œκ°€ 될 λ•Œ κΉŒμ§€, λ¬Έμ•žμ— 쀄 μ„Έμ›Œ λ†“λŠ”λ‹€. 그리고 8μ‹œκ°€ λ˜λŠ” μˆœκ°„ μ†λ‹˜λ“€μ€ λͺ¨λ‘ μž…κ΅¬μ—μ„œ 컀피λ₯Ό ν•˜λ‚˜μ”© λ°›κ³ , 자리둜 κ°„λ‹€. κ°•ν˜ΈλŠ” μž…κ΅¬μ—μ„œ 컀피λ₯Ό ν•˜λ‚˜μ”© μ£ΌλŠ” 역할을 ν•œλ‹€.μ†λ‹˜λ“€μ€ μž…κ΅¬μ— λ“€μ–΄κ°ˆ λ•Œ, κ°•ν˜Έμ—κ²Œ νŒμ„ μ€€λ‹€. μ†λ‹˜λ“€μ€ μžκΈ°κ°€ 컀피λ₯Ό λͺ‡ 번째 λ°›λŠ”μ§€μ— 따라 νŒμ„ λ‹€λ₯Έ μ•‘μˆ˜λ‘œ κ°•ν˜Έμ—κ²Œ μ€€λ‹€. 각 μ†λ‹˜μ€ κ°•ν˜Έμ—κ²Œ μ›λž˜ μ£Όλ €κ³  μƒκ°ν–ˆλ˜ 돈 - (받은 λ“±μˆ˜ - 1) 만큼의 νŒμ„ κ°•ν˜Έμ—κ²Œ μ€€λ‹€. λ§Œμ•½, μœ„μ˜ μ‹μœΌλ‘œ λ‚˜μ˜¨ 값이 음수라면, κ°•ν˜ΈλŠ” νŒμ„ 받을 수 μ—†λ‹€.예λ₯Ό λ“€μ–΄, λ―Όν˜ΈλŠ” νŒμ„ 3원 μ£Όλ €κ³  ν–ˆκ³ , μž¬ν•„μ΄λŠ” νŒμ„ 2원, μ£Όν˜„μ΄κ°€ νŒμ„ 1원 μ£Ό..

λ°˜μ‘ν˜•