[๋ฐฑ์ค€] 2467 ์šฉ์•ก (python ํŒŒ์ด์ฌ)

2022. 7. 9. 00:59ยท๐Ÿงฉ Problem Solving/[๋ฐฑ์ค€]

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

 

2467๋ฒˆ: ์šฉ์•ก

์ฒซ์งธ ์ค„์—๋Š” ์ „์ฒด ์šฉ์•ก์˜ ์ˆ˜ N์ด ์ž…๋ ฅ๋œ๋‹ค. N์€ 2 ์ด์ƒ 100,000 ์ดํ•˜์˜ ์ •์ˆ˜์ด๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ์šฉ์•ก์˜ ํŠน์„ฑ๊ฐ’์„ ๋‚˜ํƒ€๋‚ด๋Š” N๊ฐœ์˜ ์ •์ˆ˜๊ฐ€ ๋นˆ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ž…๋ ฅ๋˜๋ฉฐ, ์ด ์ˆ˜๋“ค์€ ๋ชจ๋‘ -

www.acmicpc.net


์•„์ด๋””์–ด

1. ์กฐํ•ฉ

  • ๋‹จ์ˆœํ•˜๊ฒŒ ๋ฆฌ์ŠคํŠธ์— ์žˆ๋Š” ๊ฐ’ ์ค‘์—์„œ ๋‘ ๊ฐœ๋ฅผ ๋ฝ‘์•„ ๊ณ„์‚ฐํ•˜๋Š” ์ฝ”๋“œ๋ฅผ ์งฐ๋‹ค.
  • ์‹œ๊ฐ„ ์ดˆ๊ณผ ๋ฐœ์ƒ
  • ์ƒ๊ฐํ•ด๋ณด๋‹ˆ๊นŒ ์กฐํ•ฉ์ด๋ฉด 100000C2์ธ๋ฐ 1์ดˆ๋กœ๋Š” ํƒ๋„ ์—†๋‹ค.

2. ๋ฌธ์ œ์— ์˜ค๋ฆ„์ฐจ์ˆœ์ด ํžŒํŠธ

  • ๋ฏธ๋ฆฌ ์ •๋ ฌ์ด ๋˜์–ด์žˆ์œผ๋‹ˆ๊นŒ ์ด๊ฑธ ์ด์šฉํ•˜๋ผ๋Š” ์˜๋ฏธ๋กœ ํ•ด์„
  • ์ด๋ถ„ ํƒ์ƒ‰๊ณผ ๋น„์Šทํ•˜๊ฒŒ ์ขŒ์šฐ์—์„œ ํ•˜๋‚˜์”ฉ ์ขํ˜€๊ฐ€๋ฉฐ ์ตœ์†Ÿ๊ฐ’(0์— ๊ฐ€๊นŒ์šด ๊ฐ’)์„ ์ฐพ๊ธฐ๋กœ ๊ฒฐ์ •.

 


์ฝ”๋“œ ์„ค๋ช…

while l < r:
    cur_value = dragon_liquid[l] + dragon_liquid[r]

    if abs(cur_value) <= value:
        x = dragon_liquid[l]
        y = dragon_liquid[r]
        value = abs(cur_value)

    if cur_value <= 0:
        l += 1

    else: # cur_value > 0
        r -= 1

l์€ 0, r์€ N - 1๋กœ ์„ ์–ธ. while๋ฌธ์€ l์ด r์„ ๋„˜์–ด๊ฐ€๋ฉด ์ข…๋ฃŒํ•˜๋„๋ก ํ–ˆ๋‹ค.

l๊ณผ r์— ์ž๋ฆฌ์— ์žˆ๋Š” ์šฉ์•ก์„ ํ•ฉํ•ด ๊ฐ’์„ ๊ตฌํ•œ๋‹ค. ๊ทธ ์ ˆ๋Œ“๊ฐ’์ด 0์— ๊ฐ€๊นŒ์šด ๊ฐ’์ด๋ฉด ๋‘ ์šฉ์•ก์— ๊ฐ’์„ ์ €์žฅํ•˜๊ณ  ์ตœ์†Ÿ๊ฐ’์„ ์—…๋ฐ์ดํŠธํ•ด์ค€๋‹ค.

 

๋‘ ์šฉ์•ก์˜ ํ•ฉ์ด ์Œ์ˆ˜๋ผ๋ฉด ์™ผ์ชฝ ํฌ์ธํ„ฐ๋ฅผ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ํ•œ ์นธ ์˜ฎ๊ธฐ๊ณ 

์–‘์ˆ˜๋ผ๋ฉด ์˜ค๋ฅธ์ชฝ ํฌ์ธํ„ฐ๋ฅผ ์™ผ์ชฝ์œผ๋กœ ํ•œ์นธ ์˜ฎ๊ธด๋‹ค.

 

์™œ๋ƒํ•˜๋ฉด ํ•ฉ์ด ์Œ์ˆ˜์—์„œ ์ด ๊ฐ’์„ ๋” 0์— ๊ฐ€๊น๊ฒŒ ํ•˜๋ ค๋ฉด ์ž‘์€ ๊ฐ’์„ ํฌ๊ฒŒ ํ•ด์•ผ ํ•˜๊ณ 

์–‘์ˆ˜๋ผ๋ฉด ํฐ ๊ฐ’์„ ์ž‘๊ฒŒ ํ•ด์•ผ ํ•˜๋‹ˆ๊นŒ.

 


์ „์ฒด ์ฝ”๋“œ

value = 2000000000
N = int(input())
x, y = 0, 0
l = 0
r = N - 1

dragon_liquid = [int(x) for x in input().split()]
# ๋ฌธ์ œ์—์„œ ์ด๋ฏธ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌ

while l < r:
    cur_value = dragon_liquid[l] + dragon_liquid[r]

    if abs(cur_value) <= value:
        x = dragon_liquid[l]
        y = dragon_liquid[r]
        value = abs(cur_value)

    if cur_value <= 0:
        l += 1

    else: # cur_value > 0
        r -= 1

print(x, y)

 

 

 

'๐Ÿงฉ Problem Solving > [๋ฐฑ์ค€]' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[๋ฐฑ์ค€] 12851 ์ˆจ๋ฐ”๊ผญ์งˆ 2 (python ํŒŒ์ด์ฌ)  (0) 2022.07.10
[๋ฐฑ์ค€] 1043 ๊ฑฐ์ง“๋ง (python ํŒŒ์ด์ฌ)  (0) 2022.07.09
[๋ฐฑ์ค€] 6064 ์นด์ž‰ ๋‹ฌ๋ ฅ (python ํŒŒ์ด์ฌ)  (0) 2022.07.06
[๋ฐฑ์ค€] 11403 ๊ฒฝ๋กœ์ฐพ๊ธฐ (python ํŒŒ์ด์ฌ)  (0) 2022.07.06
[๋ฐฑ์ค€] 16236 ์•„๊ธฐ ์ƒ์–ด (python ํŒŒ์ด์ฌ)  (0) 2022.07.05
'๐Ÿงฉ Problem Solving/[๋ฐฑ์ค€]' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [๋ฐฑ์ค€] 12851 ์ˆจ๋ฐ”๊ผญ์งˆ 2 (python ํŒŒ์ด์ฌ)
  • [๋ฐฑ์ค€] 1043 ๊ฑฐ์ง“๋ง (python ํŒŒ์ด์ฌ)
  • [๋ฐฑ์ค€] 6064 ์นด์ž‰ ๋‹ฌ๋ ฅ (python ํŒŒ์ด์ฌ)
  • [๋ฐฑ์ค€] 11403 ๊ฒฝ๋กœ์ฐพ๊ธฐ (python ํŒŒ์ด์ฌ)
์ œ๋ด‰์•„
์ œ๋ด‰์•„
  • ์ œ๋ด‰์•„
    Overthinking
    ์ œ๋ด‰์•„
    fake it till you make it.
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
    • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (104)
      • ๐Ÿงฉ Problem Solving (83)
        • [๋ฐฑ์ค€] (74)
        • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] (7)
        • [SW Expert Academy] (1)
        • [์•Œ๊ณ ๋ฆฌ์ฆ˜ for PS] (1)
      • ๐Ÿ“ฆ Data Structure (2)
      • ๐Ÿ“œ Language (14)
        • [python] (14)
      • ๐Ÿ–ค Git (1)
      • ๐ŸŒ† ์ผ์ƒ (2)
        • ๐Ÿ’ฌ ๋ฒฝ๋ณด๊ณ  ๋งํ•˜๊ธฐ (2)
      • ๐Ÿ—„๏ธ ๊ธฐํƒ€ (2)
      • ๐Ÿ”ต css (0)
  • ๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

    • ํ™ˆ
    • ํƒœ๊ทธ
    • ๋ฐฉ๋ช…๋ก
  • ๋งํฌ

  • ๊ณต์ง€์‚ฌํ•ญ

  • ์ธ๊ธฐ ๊ธ€

  • ํƒœ๊ทธ

    ์žฌ๊ท€
    ๋ฐ๋ธŒ์ฝ”์Šค
    ์œ„์ƒ์ •๋ ฌ
    ๋ˆ„์ ํ•ฉ
    DP
    slicing
    ํŒฐ๋ฆฐ๋“œ๋กฌ
    ๊ตฌํ˜„
    ๋ธŒ๋ฃจํŠธํฌ์Šค
    Python
    BFS
    ๋ถ„ํ•  ์ •๋ณต
    boj
    SWEA
    ๋ถ€๋ถ„ํ•ฉ
    ์ •์ฒ˜๊ธฐ
    ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ
    ํ”Œ๋กœ์ด๋“œ์›Œ์…œ
    ๋ฐฑ์ค€
    ๊ทธ๋ฆฌ๋””
    DFS
    Bruteforce
    ํŒŒ์ด์ฌ
    ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค
    ๋ฐฑํŠธ๋ž˜ํ‚น
    ๋‹ค์ต์ŠคํŠธ๋ผ
    ๋ƒ…์ƒ‰
    ์Šคํƒ
    imos
    ํˆฌํฌ์ธํ„ฐ
  • ์ตœ๊ทผ ๋Œ“๊ธ€

  • ์ตœ๊ทผ ๊ธ€

  • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.3
์ œ๋ด‰์•„
[๋ฐฑ์ค€] 2467 ์šฉ์•ก (python ํŒŒ์ด์ฌ)
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”