๐Ÿค–/๋ฐฑ์ค€ 109

๋ฐฑ์ค€ 21921: ๋ธ”๋กœ๊ทธ (Python)

https://www.acmicpc.net/problem/21921 21921๋ฒˆ: ๋ธ”๋กœ๊ทธ ์ฒซ์งธ ์ค„์— $X$์ผ ๋™์•ˆ ๊ฐ€์žฅ ๋งŽ์ด ๋“ค์–ด์˜จ ๋ฐฉ๋ฌธ์ž ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ๋งŒ์•ฝ ์ตœ๋Œ€ ๋ฐฉ๋ฌธ์ž ์ˆ˜๊ฐ€ 0๋ช…์ด๋ผ๋ฉด SAD๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ๋งŒ์•ฝ ์ตœ๋Œ€ ๋ฐฉ๋ฌธ์ž ์ˆ˜๊ฐ€ 0๋ช…์ด ์•„๋‹Œ ๊ฒฝ์šฐ ๋‘˜์งธ ์ค„์— ๊ธฐ๊ฐ„์ด ๋ช‡ ๊ฐœ ์žˆ๋Š”์ง€ ์ถœ๋ ฅํ•œ๋‹ค www.acmicpc.net ํˆฌ ํฌ์ธํ„ฐ ์ด์šฉ n, x = map(int, input().split()) visitors = list(map(int, input().split())) i = j = 0 temp = result = 0 cnt = 0 for i in range(n): # ๋ ํฌ์ธํ„ฐ ์ด๋™ while j-i < x and j < n: temp += visitors[j] j += 1 # x์ผ if j-i == x..

๋ฐฑ์ค€ 16918: ๋ด„๋ฒ„๋งจ (Python)

https://www.acmicpc.net/problem/16918 16918๋ฒˆ: ๋ด„๋ฒ„๋งจ ์ฒซ์งธ ์ค„์— R, C, N (1 ≤ R, C, N ≤ 200)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ R๊ฐœ์˜ ์ค„์— ๊ฒฉ์žํŒ์˜ ์ดˆ๊ธฐ ์ƒํƒœ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋นˆ ์นธ์€ '.'๋กœ, ํญํƒ„์€ 'O'๋กœ ์ฃผ์–ด์ง„๋‹ค. www.acmicpc.net n=0์ผ ๋•Œ: ํญํƒ„ ์„ค์น˜ n=1์ผ ๋•Œ: ๊ทธ๋Œ€๋กœ n=2์ผ ๋•Œ~: ๋‚˜๋จธ์ง€ ๋ชจ๋“  ์นธ์— ํญํƒ„ ์„ค์น˜ -> ํญ๋ฐœ ๋ฐ˜๋ณต r*c ํฌ๊ธฐ์˜ bombs ๋ฐฐ์—ด์„ ๋ชจ๋‘ 0์œผ๋กœ ์ดˆ๊ธฐํ™”ํ•˜๊ณ , ์ดˆ๊ธฐ ์ƒํƒœ ๋ฐฐ์—ด์„ ์ž…๋ ฅ๋ฐ›์œผ๋ฉด์„œ 'O'์ธ ๋ถ€๋ถ„์€ 2๋กœ ๋ฐ”๊ฟ”์ค€๋‹ค. (0์ดˆ - 1์ดˆ ์ƒํƒœ) i=2๋ถ€ํ„ฐ n+1๊นŒ์ง€ for๋ฌธ์„ ๋Œ๋ ค์ฃผ๋ฉด์„œ 1. bombs ์ˆœํšŒํ•˜๋ฉด์„œ ๊ฐ’์„ ํ•˜๋‚˜์”ฉ ๊ฐ์†Œ์‹œํ‚ค๊ณ , 2. i๊ฐ€ ์ง์ˆ˜์ผ ๋•Œ์—๋Š” ๋ชจ๋“  ์นธ์— ํญํƒ„ ์„ค์น˜ -> 0์ธ ๋ถ€๋ถ„์„ 3์œผ๋กœ ..

๋ฐฑ์ค€ 12933: ์˜ค๋ฆฌ (Python)

https://www.acmicpc.net/problem/12933 12933๋ฒˆ: ์˜ค๋ฆฌ ์ฒซ์งธ ์ค„์— ์˜์„ ์ด๊ฐ€ ๋…น์Œํ•œ ์†Œ๋ฆฌ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์†Œ๋ฆฌ์˜ ๊ธธ์ด๋Š” 5๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 2500๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๊ณ , 'q','u','a','c','k'๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. www.acmicpc.net ๋กœ์ง์€ ์ด๋Ÿฌํ•จ.. ์ด๋•Œ๊นŒ์ง€๋งŒ ํ•ด๋„ ์‰ฌ์šด ๋ฌธ์ œ์ธ ์ค„ ์•Œ์•˜์ง€.. ์ฒซ ์‹œ๋„ (์‹คํŒจ) sound๋ฅผ ์ฐจ๋ก€๋Œ€๋กœ ์ˆœํšŒํ•˜๋ฉด์„œ q -> u -> a -> c -> k ์— ํ•ด๋‹นํ•˜๋ฉด ๋„˜์–ด๊ฐ€๊ณ , ํ•ด๋‹นํ•˜์ง€ ์•Š์œผ๋ฉด temp ๋ฐฐ์—ด์— ๋ฌธ์ž๋ฅผ ๋„ฃ๋Š”๋‹ค. ์ˆœํšŒ๊ฐ€ ๋๋‚œ ํ›„ sound์™€ temp๊ฐ€ ๊ฐ™๋‹ค๋ฉด (q-u-a-c-k๋ฅผ ์ฐพ์ง€ ๋ชปํ•œ ๊ฒฝ์šฐ) breakํ•ด์ฃผ๊ณ , ๊ฐ™์ง€ ์•Š๋‹ค๋ฉด sound = temp ํ›„ ์ •๋‹ต์„ ํ•˜๋‚˜์”ฉ ์ถ”๊ฐ€ํ–ˆ๋‹ค. sound = input() du..

๋ฐฑ์ค€ 1766: ๋ฌธ์ œ์ง‘ (Python)

https://www.acmicpc.net/problem/1766 1766๋ฒˆ: ๋ฌธ์ œ์ง‘ ์ฒซ์งธ ์ค„์— ๋ฌธ์ œ์˜ ์ˆ˜ N(1 ≤ N ≤ 32,000)๊ณผ ๋จผ์ € ํ‘ธ๋Š” ๊ฒƒ์ด ์ข‹์€ ๋ฌธ์ œ์— ๋Œ€ํ•œ ์ •๋ณด์˜ ๊ฐœ์ˆ˜ M(1 ≤ M ≤ 100,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ M๊ฐœ์˜ ์ค„์— ๊ฑธ์ณ ๋‘ ์ •์ˆ˜์˜ ์ˆœ์„œ์Œ A,B๊ฐ€ ๋นˆ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ www.acmicpc.net ์œ„์ƒ์ •๋ ฌ์„ ์ด์šฉํ•ด์„œ ํ’€๋ฉด ๋˜๋Š”๋ฐ '๋จผ์ € ํ‘ธ๋Š” ๊ฒƒ์ด ์ข‹์€ ๋ฌธ์ œ'์— ๋Œ€ํ•œ ์ •๋ณด๋ฅผ ๊ฐ„์„ ์œผ๋กœ ์ €์žฅํ•˜๊ณ  ๊ฐ€๋Šฅํ•˜๋ฉด ์‰ฌ์šด ๋ฌธ์ œ๋ฅผ ๋จผ์ € ํ’€์–ด์•ผ ํ•˜๋Š”๋ฐ ๋‚œ์ด๋„๋Š” 1๋ฒˆ~n๋ฒˆ ์ฐจ๋ก€๋Œ€๋กœ ๋˜์–ด ์žˆ์œผ๋‹ˆ ํ๋ฅผ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•ด์„œ ์“ฐ๋ฉด ๋œ๋‹ค. -> ์šฐ์„ ์ˆœ์œ„ ํ ์‚ฌ์šฉํ•จ # ์šฐ์„ ์ˆœ์œ„ํ from queue import PriorityQueue # ์ƒ์„ฑ q = PriorityQueue() q = Pr..

๋ฐฑ์ค€ 2252: ์ค„ ์„ธ์šฐ๊ธฐ (Python)

https://www.acmicpc.net/problem/2252 2252๋ฒˆ: ์ค„ ์„ธ์šฐ๊ธฐ ์ฒซ์งธ ์ค„์— N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)์ด ์ฃผ์–ด์ง„๋‹ค. M์€ ํ‚ค๋ฅผ ๋น„๊ตํ•œ ํšŒ์ˆ˜์ด๋‹ค. ๋‹ค์Œ M๊ฐœ์˜ ์ค„์—๋Š” ํ‚ค๋ฅผ ๋น„๊ตํ•œ ๋‘ ํ•™์ƒ์˜ ๋ฒˆํ˜ธ A, B๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด๋Š” ํ•™์ƒ A๊ฐ€ ํ•™์ƒ B์˜ ์•ž์— ์„œ์•ผ ํ•œ๋‹ค๋Š” ์˜ www.acmicpc.net import sys from collections import deque input = sys.stdin.readline n, m = map(int, input().split()) students = [[] for _ in range(n+1)] # ๊ฐ„์„ ์— ๋Œ€ํ•œ ์ •๋ณด (์ˆœ์„œ ์ €์žฅ) indegree = [0] * (n+1) # ์ง„์ž…์ฐจ์ˆ˜ for _ in ran..

๋ฐฑ์ค€ 2887: ํ–‰์„ฑ ํ„ฐ๋„ (Python)

https://www.acmicpc.net/problem/2887 2887๋ฒˆ: ํ–‰์„ฑ ํ„ฐ๋„ ์ฒซ์งธ ์ค„์— ํ–‰์„ฑ์˜ ๊ฐœ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 100,000) ๋‹ค์Œ N๊ฐœ ์ค„์—๋Š” ๊ฐ ํ–‰์„ฑ์˜ x, y, z์ขŒํ‘œ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ขŒํ‘œ๋Š” -109๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 109๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ •์ˆ˜์ด๋‹ค. ํ•œ ์œ„์น˜์— ํ–‰์„ฑ์ด ๋‘ ๊ฐœ ์ด www.acmicpc.net ์ฒ˜์Œ์—๋Š” 1774๋ฒˆ(์šฐ์ฃผ์‹ ๊ณผ์˜ ๊ต๊ฐ) ๋ฌธ์ œ์ฒ˜๋Ÿผ ๋น„์šฉ์— ๋”ฐ๋ฅธ ๊ฐ„์„ ์„ ๋ชจ๋‘ ์ •์˜ํ•ด์ฃผ์—ˆ๋‹ค. ํ•˜์ง€๋งŒ ๋ฌธ์ œ ์กฐ๊ฑด์—์„œ n์˜ ์ˆ˜๊ฐ€ ๊ต‰์žฅํžˆ ํฌ๊ธฐ ๋•Œ๋ฌธ์— ๋ฉ”๋ชจ๋ฆฌ ์ดˆ๊ณผ๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค. import sys input = sys.stdin.readline def find(parent, x): if parent[x] != x: parent[x] = find(parent, parent[x]) ..

๋ฐฑ์ค€ 1774: ์šฐ์ฃผ์‹ ๊ณผ์˜ ๊ต๊ฐ (Python)

https://www.acmicpc.net/problem/1774 1774๋ฒˆ: ์šฐ์ฃผ์‹ ๊ณผ์˜ ๊ต๊ฐ (1,1) (3,1) (2,3) (4,3) ์ด๋ ‡๊ฒŒ ์šฐ์ฃผ์‹ ๋“ค๊ณผ ํ™ฉ์„ ์ž์”จ์˜ ์ขŒํ‘œ๊ฐ€ ์ฃผ์–ด์กŒ๊ณ  1๋ฒˆํ•˜๊ณ  4๋ฒˆ์ด ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋‹ค. ๊ทธ๋ ‡๋‹ค๋ฉด 1๋ฒˆํ•˜๊ณ  2๋ฒˆ์„ ์ž‡๋Š” ํ†ต๋กœ๋ฅผ ๋งŒ๋“ค๊ณ  3๋ฒˆํ•˜๊ณ  4๋ฒˆ์„ ์ž‡๋Š” ํ†ต๋กœ๋ฅผ ๋งŒ๋“ค๋ฉด ์‹ ๋“ค๊ณผ ์„ ์ž์”จ๋ผ www.acmicpc.net ํฌ๋ฃจ์Šค์นผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์—์„œ ์ด๋ฏธ ์—ฐ๊ฒฐ๋œ ๋…ธ๋“œ๋“ค์„ ๋ฏธ๋ฆฌ ์—ฐ๊ฒฐํ•ด์ฃผ๊ณ  ๋…ธ๋“œ๋“ค์˜ ๊ฐ„์„ ์„ ์ง์ ‘ ์ •์˜ํ•ด์ฃผ๋ฉด ๋˜๋Š” ๋ฌธ์ œ๋‹ค ์ฒ˜์Œ ์ƒ๊ฐํ–ˆ๋˜ ๊ฑด ์ด๋ฏธ ์—ฐ๊ฒฐ๋œ ํ†ต๋กœ๋“ค์„ ๋”ฐ๋กœ ์ €์žฅํ•˜๊ณ  ํ•ฉ์นœ ํ›„ ๊ทธ ํ†ต๋กœ๋“ค์„ ๋นผ๊ณ  ๊ฐ„์„ ๋“ค์„ ๋ชจ๋‘ ๋Œ๋ฉด์„œ unionํ•˜๋Š” ๊ฑฐ์˜€๋Š”๋ฐ ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋–ด๋‹คใ…  def find(parent, x): if parent[x] != x: parent[x] = find(parent, pare..

๋ฐฑ์ค€ 1197: ์ตœ์†Œ ์ŠคํŒจ๋‹ ํŠธ๋ฆฌ (Python)

https://www.acmicpc.net/problem/1197 1197๋ฒˆ: ์ตœ์†Œ ์ŠคํŒจ๋‹ ํŠธ๋ฆฌ ์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ V(1 ≤ V ≤ 10,000)์™€ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ E(1 ≤ E ≤ 100,000)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ E๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ ๊ฐ„์„ ์— ๋Œ€ํ•œ ์ •๋ณด๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ์„ธ ์ •์ˆ˜ A, B, C๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด๋Š” A๋ฒˆ ์ •์ ๊ณผ B๋ฒˆ ์ •์ ์ด www.acmicpc.net ์ผ๋ฐ˜์ ์ธ ํฌ๋ฃจ์Šค์นผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ํ’€๋ฉด ๋œ๋‹ค. 1. ๊ฐ„์„  -> ๋น„์šฉ ๊ธฐ์ค€ ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ 2. ์‚ฌ์ดํด์ด ๋ฐœ์ƒํ•˜์ง€ ์•Š์œผ๋ฉด(= parent๊ฐ€ ๊ฐ™์ง€ ์•Š์œผ๋ฉด) union ํ•œ๋ฒˆ ์—๋Ÿฌ๋‚ฌ์—ˆ๋Š”๋ฐ,,, ์–ด์ด์—†๊ฒŒ๋„ cost ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค๋Š” ์ƒ๊ฐ์— ์‚ฌ๋กœ์žกํ˜€์„œ ๊ฐ„์„ ์— ๋Œ€ํ•œ ์ •๋ณด a, b, c๋ฅผ ์ž…๋ ฅ ๋ฐ›์„ ๋•Œ c, a, b๋กœ ์ž…๋ ฅ๋ฐ›์Œ,,ใ…Ž ์‹ค์ˆ˜ํ•˜์ง€ ๋ง์ž import sys s..

๋ฐฑ์ค€ 4195: ์นœ๊ตฌ ๋„คํŠธ์›Œํฌ (Python)

https://www.acmicpc.net/problem/4195 4195๋ฒˆ: ์นœ๊ตฌ ๋„คํŠธ์›Œํฌ ์ฒซ์งธ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ฒซ์งธ ์ค„์—๋Š” ์นœ๊ตฌ ๊ด€๊ณ„์˜ ์ˆ˜ F๊ฐ€ ์ฃผ์–ด์ง€๋ฉฐ, ์ด ๊ฐ’์€ 100,000์„ ๋„˜์ง€ ์•Š๋Š”๋‹ค. ๋‹ค์Œ F๊ฐœ์˜ ์ค„์—๋Š” ์นœ๊ตฌ ๊ด€๊ณ„๊ฐ€ ์ƒ๊ธด ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„ www.acmicpc.net ์ž…๋ ฅ๋ฐ›๋Š” ์š”์†Œ๊ฐ€ ์‚ฌ๋žŒ์ด๋ฆ„์ด๊ธฐ ๋•Œ๋ฌธ์— ์ˆซ์ž๋กœ ๊ด€๋ฆฌํ•˜๊ธฐ ์œ„ํ•ด ๋”•์…”๋„ˆ๋ฆฌ(people)๋ฅผ ์„ ์–ธํ•˜๊ณ  1. a, b ์ž…๋ ฅ๋ฐ›์•„์„œ 2. ๋”•์…”๋„ˆ๋ฆฌ์— ์กด์žฌํ•˜์ง€ ์•Š์œผ๋ฉด ์ถ”๊ฐ€, parent ์ถ”๊ฐ€ 3. union ๊ทธ ํ›„ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ์š”์†Œ๋“ค์˜ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๊ธฐ ์œ„ํ•ด ์›๋ž˜ count ํ•จ์ˆ˜๋ฅผ ์ผ๋Š”๋ฐ ์ œ๋Œ€๋กœ ๋ชป ์žก์•„๋‚ด๊ธธ๋ž˜ for๋ฌธ์„ ์ผ๋‹ค ใ…Žใ…Ž์‹œ๊ฐ„์ดˆ๊ณผ import sys sys.setrecursionlimit(1000..

๋ฐฑ์ค€ 1976: ์—ฌํ–‰ ๊ฐ€์ž (Python)

https://www.acmicpc.net/problem/1976 1976๋ฒˆ: ์—ฌํ–‰ ๊ฐ€์ž ๋™ํ˜์ด๋Š” ์นœ๊ตฌ๋“ค๊ณผ ํ•จ๊ป˜ ์—ฌํ–‰์„ ๊ฐ€๋ ค๊ณ  ํ•œ๋‹ค. ํ•œ๊ตญ์—๋Š” ๋„์‹œ๊ฐ€ N๊ฐœ ์žˆ๊ณ  ์ž„์˜์˜ ๋‘ ๋„์‹œ ์‚ฌ์ด์— ๊ธธ์ด ์žˆ์„ ์ˆ˜๋„, ์—†์„ ์ˆ˜๋„ ์žˆ๋‹ค. ๋™ํ˜์ด์˜ ์—ฌํ–‰ ์ผ์ •์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ด ์—ฌํ–‰ ๊ฒฝ๋กœ๊ฐ€ ๊ฐ€๋Šฅํ•œ ๊ฒƒ์ธ www.acmicpc.net ๋ฌธ์ œ์˜ ํ•ด๊ฒฐ๋ฒ•์€ ์‰ฝ๊ฒŒ ์ƒ๊ฐํ•ด๋‚ผ ์ˆ˜ ์žˆ์—ˆ๋‹ค. ์ž…๋ ฅ๋œ ์—ฌํ–‰ ๊ณ„ํš์˜ ๋„์‹œ๋“ค์ด ์„œ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š”์ง€๋งŒ ํ™•์ธํ•˜๋ฉด ๋œ๋‹ค. ๋„์‹œ๋“ค์˜ ์—ฐ๊ฒฐ ์ •๋ณด๋ฅผ ์ž…๋ ฅ๋ฐ›์„ ๋•Œ 1์ด๋ฉด unionํ•ด์ค€๋‹ค. ๊ณ„ํš์„ ์ž…๋ ฅ๋ฐ›์€ ํ›„ ์‹œ๊ฐ„์„ ์ค„์ด๊ธฐ ์œ„ํ•ด ๋ฆฌ์ŠคํŠธ์—์„œ ์ค‘๋ณต ์›์†Œ๋ฅผ ์ œ๊ฑฐํ•ด์ฃผ๊ณ  find๋ฅผ ํ†ตํ•ด ๋ชจ๋‘ ๊ฐ™์€ ๋ถ€๋ชจ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋Š”์ง€(= ํ•˜๋‚˜์˜ ์ง‘ํ•ฉ์ธ์ง€) ํ™•์ธํ•ด์ฃผ๋ฉด ๋œ๋‹ค. def find_parent(parent, x): if parent[..