Manasa and Stones

https://www.hackerrank.com/challenges/manasa-and-stones/problem?isFullScreen=true

Manasa and Stones | HackerRank

 

나의 코드

#!/bin/python3

import math
import os
import random
import re
import sys

def dfs(dfs_n, a, b, now_n, end_dfs_n):
    answer = set()
    if dfs_n == end_dfs_n:
        return {now_n}
    else:
        answer = answer.union(dfs(dfs_n+1, a, b, now_n+a, end_dfs_n))
        answer = answer.union(dfs(dfs_n+1, a, b, now_n+b, end_dfs_n))
    return answer

def stones(n, a, b):
    result = dfs(0, a, b, 0, n-1)
    return sorted(result)

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    T = int(input().strip())
    for T_itr in range(T):
        n = int(input().strip())
        a = int(input().strip())
        b = int(input().strip())
        result = stones(n, a, b)
        fptr.write(' '.join(map(str, result)))
        fptr.write('\n')
        
    fptr.close()

 

시간 복잡도

dfs로 접근하였기에 n 깊이 만큼 두가지 선택지를 가짐
answer = answer.union(dfs(dfs_n+1, a, b, now_n+a, end_dfs_n))
answer = answer.union(dfs(dfs_n+1, a, b, now_n+b, end_dfs_n))
즉, 지수형 시간 복잡도를 가짐 O(2**n)

 

 

수정 코드

#!/bin/python3

import math
import os
import random
import re
import sys

def stones(n, a, b):
    possible_stones = set()

    for i in range(n):
        stone_value = i * a + (n - 1 - i) * b
        possible_stones.add(stone_value)
    
    return sorted(possible_stones)

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    T = int(input().strip())
    for T_itr in range(T):
        n = int(input().strip())
        a = int(input().strip())
        b = int(input().strip())
        result = stones(n, a, b)
        fptr.write(' '.join(map(str, result)))
        fptr.write('\n')
    fptr.close()

 

시간 복잡도

for i in range(n) : n 만큼 순회 하므로 ( 선형 시간 복잡도 )
return sorted(possible_stones) :  최종적으로 정렬해 return 하므로 ( 선형로그 시간 복잡도 )
해당 알고리즘 시간복잡도는 선형로그 시간 복잡도 ( O(nlogn) )