백준_1789_수들의 합

임정민·2022년 11월 27일
2

알고리즘 문제풀이

목록 보기
7/173
post-thumbnail

코딩테스트 연습 스터디 진행중 입니다. ✍✍✍
Notion : https://www.notion.so/1c911ca6572e4513bd8ed091aa508d67

문제

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

풀이

[나의 풀이1]

S = int(input())
answer = 0
for n in range(1,S+1):
    if n*(n+1)/2 > S :
        answer = n - 1
        break
    elif n*(n+1)/2 == S:
        answer = n
print(answer)

[나의 풀이2]

(시간초과)

S = int(input())

answer = 0
tmp = [-1]

for n in range(2,S+1):
    tmp.append(n-1)
    tmp.sort()
    tmp.append(S-sum(tmp[1:len(tmp)+1]))
    tmp.sort()
    print(f"n = {n}, {tmp}")

    print("-----")
    print(tmp[1:])
    print("-----")
    
    if tmp.pop() == n - 1 :
        answer = n - 1
        break
       
print(answer)

[팀원의 풀이1]

# coding = utf-8

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    def getdata():
        n = int(input())
        return n

    n = getdata()
    res = 0
    i = 1
    while True :
        res += i
        if res > n :
            res -= i
            i -= 1
            break
        i += 1
    print(i)

[팀원의 풀이2]

# coding = utf-8

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    def getdata():
        n = int(input())
        return n

    n = getdata()
    res = 0
    i = 1
    while res<=n :
        res += i
        i += 1
    print(i-2)

[팀원의 풀이3]

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline
    import math
    a = int(input())
    b = int(math.sqrt(a*2))
    c = int(math.sqrt(a*2-b))
    if b!=c :
        print(c)
    else:
        print(b)

[팀원의 풀이4]

import math

a = int(input())
b = math.sqrt(a*2)
if b%1 == 0:
	  print(int(b-1))
else:
		print(int(b))

메모

  1. 핵심은 1부터 n까지 입력값보다 커질 때까지 더하는 것

나의 경우 2가지 방식으로 풀었는데 첫번째로는 수열의 합공식 n(n+1)/2 을 활용하여 입력값까지 도달하였다. 두번째 방식은 시간초과가 났다. 리스트안에 1부터 n까지 요소를 추가하고 추가한 값을 모두 더하여 입력값을 뺀 값을 맨뒤에 추가하는 형식으로 답을 구하였다. 하지만 이 방식은 append를 활용했기 때문에 시간이 오래걸리는 방식이였다. 앞으로 알고리즘 문제 풀 때 append는 지양해야함을 느꼈다.

  1. syswithline 사용
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    def getdata():
        n = int(input())
        return n

    n = getdata()
	
    ~풀이~
    
    print(~~)

팀원들의 풀이 중 위와 같은 방식으로 입력값을 받고 답을 출력하는 팀원이 있었다. syswithline을 활용하면 시간을 좀 더 단축할 수 있다고 하니 앞으로 애용해야겠다.

  1. 삼각수의 개념

삼각수를 활용한 풀이 방법이 있었다. 아직은 이해가 가지않아 팀원에게 물어보고 다시 작성할 예정이다.

감사합니다.🐮🐮🐮

profile
https://github.com/min731

0개의 댓글