반응형

유형 : 이분탐색

문제풀이:

 모든 요소 i*j를 리스트에 넣고 정렬해서 K번째를 반환하면 시간복잡도가 O(N^2)이 되어 시간초과가 뜬다. 따라서 다른 방법을 생각해야 한다.

1. N*N행렬이라 하면, 1번째 행(1부터)의 요소는 [1, 2, ... , N]이 되고, 2번째 행의 요소는 [2*1, 2*2, ..., 2*N]이 된다. 즉, i번째 행의 요소는 [i*1, i*2, ... i*N]이 되고, i번째 행에는 어떤 값 x보다 작은 값이 x//i개 (x가 i*N보다 큰 경우에는 N개) 존재하게 된다.

2. 따라서 N*N행렬에서 x보다 작은 값은 모든 i(1~N)에 대한 x//i의 합이 된다.

3. 이 값을 check(x)라 하면, x를 1과 N^2 사이에서 이분탐색하며 check(x)가 K보다 크거나 같은 가장 작은 값을 반환한다.

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
n=int(input())
k=int(input())
 
def check(mid):
    num = 0
    for i in range(1,n+1):
        num+=min(mid//i,n)
    return num
 
def binSearch(n,k):
    l,r=0,k
    mid=(l+r)//2
    while l<=r:
        mid=(l+r)//2
        num = check(mid)
        if num >= k:
            r=mid-1
        else:
            l=mid+1
    if check(mid)<k:
        mid+=1
    print(mid)            
    
binSearch(n,k)
 cs

line 6의 for문이 과정2가 된다.

문제 링크

 

1300번: K번째 수

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B의 인덱스는 1부터 시작한다.

www.acmicpc.net

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 2468 안전 영역  (0) 2020.03.17
백준 2467 용액  (0) 2020.03.12
백준 17214 다항 함수의 적분  (0) 2020.03.10
백준 2869 달팽이는 올라가고 싶다  (0) 2020.03.09
백준 1890 점프  (0) 2020.03.09
반응형

문제풀이

1. start를 전에 "+" 또는 "-" 연산자의 인덱스라고 하면, end는 start 이후의 첫 "+" 또는 "-" 연산자가 있는 인덱스입니다.

2. start부터 end까지의 sub string을 term 이라 하면, terms에서 x의 개수와 계수를 찾아줍니다. 계수는 맨앞에서부터 term의 length에서 x의 개수를 빼준 값까지의 term의 sub string이 됩니다. 예를들면, 6xx라 하면 len(term)은 3이고, xx는 2 이므로 term[:3-2]를 해준 후 정수로 파싱해주면 됩니다. x의 개수의 경우, 저는 collections.Counter를 사용하였습니다. 계수가 존재하지 않는 경우에는 1이 됩니다.

3. 적분한 값의 계수는 원래 계수를 x의 개수에서 1을 더해준 값으로 나누어준 값이 됩니다. 또한, 적분한 계수가 1이라면 생략해주어야합니다. 또한 뒤에 x를 하나 더 붙여주면 됩니다.

 

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import collections
 
eq = input()
 
def integrate(term):
    t_dic = collections.Counter(term)
    a=term[:len(term)-t_dic["x"]]
    a = int(a) if len(a) != 0 else 1
    
    b = str(a//(t_dic["x"]+1))
    result = b + "x" * (t_dic["x"]+1) if b != "1" else "x" * (t_dic["x"]+1)
    return result
 
op = ["+","-"]
if eq[0] in op:
    answer = eq[0]
    start = 1
    end = 1
else :
    answer = ""
    start = 0
    end = 0
if eq[start] == "0":
    print("W")
else:
    while end < len(eq):
        if eq[end] not in op:
            end += 1
        else:
            answer += integrate(eq[start:end])
            #부호
            answer += eq[end]
            start = end + 1
            end += 1
    answer += integrate(eq[start:])+"+W"
    print(answer)
 cs

line 15 : 주어진 식이 "-"로 시작하는 경우입니다.

line 30 : term으로 주어지는 eq[start:end]는 부호를 제외한 숫자와 x만으로 구성된 항입니다. 부호의 경우 line 32에서 뒤의 부호를 붙여주게 됩니다.

line 35 : 저처럼 풀 경우에는 마지막 항이 while문에서 처리되지 않으므로, 따로 처리해주어야합니다.

line 23 : 0이 입력값으로 주어지는 경우 0x+W로 반환되는 것에 대한 예외처리입니다.

문제링크

 

17214번: 다항 함수의 적분

첫째 줄에 최대 일차 일변수 다항식이 주어진다. 항의 개수는 최대 2개이고, 변수는 항상 x로 주어지며, 각 항은 공백 문자로 구분되지 않는다. 주어지는 계수는 절댓값이 10,000을 넘지 않는 0이 아닌 2의 배수이고 주어지는 상수는 절댓값이 10,000을 넘지 않는 정수이다. 차수가 같은 항은 한 번만 주어진다. 단, 계수의 절댓값이 1인 경우에는 1을 생략한다. 다항식은 차수가 큰 것부터 작아지는 순서대로 주어진다.

www.acmicpc.net

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 2467 용액  (0) 2020.03.12
백준 1300 K번째 수  (0) 2020.03.11
백준 2869 달팽이는 올라가고 싶다  (0) 2020.03.09
백준 1890 점프  (0) 2020.03.09
백준 17478 재귀함수가 뭔가요?  (0) 2020.03.08
반응형

13199 치킨 먹고 싶다 문제가 안풀려서 고생하다가 이 문제의 어려운 버전이라는 글이 있어서 이 문제부터 풀어보았는데, 이 문제는 너무 쉬웠다...

문제풀이

1일차 잠들기 전 높이는 A

2일차 잠들기 전 높이는 2A-B

3일차 잠들기 전 높이는 3A-2B

즉, N일차 잠들기 전의 높이는 NA-(N-1)B이고 NA-(N-1)B>V인 N의 최솟값을 찾으면 된다.

위의 식을 N에 대하여 정리하면 

N = (V-B)/(A-B)

 

Python Code

1
2
3
4
5
6
import sys,math
 
a,b,v = map(int,sys.stdin.readline().split())
 
n = (v-b)/(a-b)
print(math.ceil(n))
 cs

 

문제링크

 

2869번: 달팽이는 올라가고 싶다

문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) 출력 첫째 줄에 달팽

www.acmicpc.net

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 1300 K번째 수  (0) 2020.03.11
백준 17214 다항 함수의 적분  (0) 2020.03.10
백준 1890 점프  (0) 2020.03.09
백준 17478 재귀함수가 뭔가요?  (0) 2020.03.08
백준 2293 동전 1  (0) 2020.03.01
반응형

유형 : dp

 

 처음에는 dfs를 이용하여 모든 경로를 탐색했으나 당연히 시간초과가 나왔다.

문제풀이

1. dp를 활용해야 하는데, dp[r][c]는 (r,c)에 올 수 있는 경우의 수이다. (r,c)에서 갈 수 있는 길이가 a라 하면, (r+a,c), (r,c+a) 두 가지 경우가 가능하다. 두 경우 가능한 경우의 dp 값에 dp[r][c]를 더해주면 된다.

2. 1의 과정을 (0,0)부터 (n-1,n-1)까지 반복한다.

 

요약

 모든 경로를 다 고려할 필요 없이, dp를 이용하여 (r,c)에서 (r',c')으로 이동한다고 하면, dp[r'][c'] += dp[r][c]를 해주면 중복되는 경로들을 다시 탐색하지 않아도 된다.

 

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import sys
def solution():
    dp[0][0] = 1
    for r in range(n):
        for c in range(n):
            l = maps[r][c]
            if l == 0 or dp[r][c] == 0 :
                continue
            new_r = r+l
            new_c = c+l
            if new_r < n:
                dp[new_r][c] += dp[r][c]
            if new_c < n:
                dp[r][new_c] += dp[r][c]
    print(dp[n-1][n-1])
if __name__=="__main__":
    n = int(sys.stdin.readline())
    maps = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
    dp=[[0 for i in range(n)] for j in range(n)]
    solution()
 cs

line 3 : 0,0에서 시작할 것이니, dp[0][0]은 0이 아닌 1로 해주어야한다.

line 7 : (r,c)에서 갈 수 있는 경우가 0이거나 (r,c)에 도착 할 수 있는 경우의 수가 0이라면 고려할 필요가 없다.

line 12, 14 : 위에서 언급한 dp[r'][c'] += dp[r][c] 과정.

 

 길이가 N인 정사각형에 대하여 이중 포문을 도므로 시간복잡도는 O(N^2)이 된다.

문제 링크

 

1890번: 점프

문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로

www.acmicpc.net

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 17214 다항 함수의 적분  (0) 2020.03.10
백준 2869 달팽이는 올라가고 싶다  (0) 2020.03.09
백준 17478 재귀함수가 뭔가요?  (0) 2020.03.08
백준 2293 동전 1  (0) 2020.03.01
백준 1038 감소하는 수  (0) 2020.02.28
반응형

재귀함수

 함수 안에서 자기 자신을 다시 호출하는 함수로, 무한 루프에 빠지지 않기 위해서는 더이상 자기자신을 호출하지 않는 종료 조건을 잘 정해야 한다.

문제풀이

 입력받은 N만큼 자기 자신을 호출하면 되므로, 재귀함수의 파라미터로 목표 depth와 현재 depth를 준 후, 자기 자신을 호출할 때는 depth에 1을 더해서 호출한다.

 depth가 N보다 작은 경우에는 아래의 글들을 프린트하되, 각 문장 앞에 ____를 depth번 반복하여 프린트 한 후, depth에 1을 더해서 자기자신을 다시 호출한다.

 

"재귀함수가 뭔가요?"

"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.

마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.

그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."

 

 반면 depth가 N일 경우에는 아래의 문장 앞에 ____를 depth번 반복하여 프린트하고, 함수 호출은 하지 않는다.

 

"재귀함수가 뭔가요?"

"재귀함수는 자기 자신을 호출하는 함수라네"

 

마지막으로, 모든 depth에서 위의 경우에는 함수 호출을 한 후, 아래 경우에는 주어진 두 줄을 프린트 한 후 앞에 ____를 depth번 반복하여 프린트 한후, 아래의 문장을 프린트한다.

 

라고 답변하였지.

 

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
a="\"재귀함수가 뭔가요?\""
b="\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어."
c="마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지."
d="그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\""
last_b="\"재귀함수는 자기 자신을 호출하는 함수라네\""
dap="라고 답변하였지."
bar="____"
def recur(goal, now):
    temp = bar*now
    print(temp+a)
    if now < goal:
        print(temp+b)
        print(temp+c)
        print(temp+d)
        recur(goal,now+1)
    else:
        print(temp+last_b)
    print(temp+dap)
if __name__ == "__main__":
    n = int(input())
    print("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.")
    recur(n,0)
 cs

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 2869 달팽이는 올라가고 싶다  (0) 2020.03.09
백준 1890 점프  (0) 2020.03.09
백준 2293 동전 1  (0) 2020.03.01
백준 1038 감소하는 수  (0) 2020.02.28
백준 2157 여행  (0) 2020.02.27
반응형

문제풀이

 works의 요소들의 제곱의 합이 가장 작게 하면 되는 문제로, works 요소들에서 주어진 n만큼을 적절히 빼서 works의 요소들의 최댓값을 가장 작게 만들어주면 된다. 따라서 가장 단순한 풀이로는, works를 정렬해가며 최댓값인 요소에서 1씩 빼는 과정을 n번 반복하면 된다. 

 하지만 위와 같은 방법으로 풀게되면, 당연히 효율이 좋지 못하므로, 더 효율적인 풀이를 고려해야한다. 제 풀이는 다음과 같습니다.

 1. works를 정렬한 후, i를 1씩 늘려가며 works의 i-1번째 요소까지의 모든 요소들의 값을 같게 하는데,

 1-1. 만약 works의 0번째부터 i-1번째 요소들을 모두 i번째 요소와 같도록 만들 수 있다면 바꾼 후, 바꿔준 만큼 n에서 빼줍니다.

 1-2. 불가능하다면 1과정을 멈춘다.

 2. 1-1을 거쳐 값을 똑같이 맞춰줄 수 있었던 요소들에 대하여 남은 n을 공평하게 배분한다.

 3. 남은 값들을 앞에서부터 1씩 배분한다.

 

예시

 works = [3,5,7], n = 3인 경우를 예로 들어보면 다음과 같다.

t n works[0] works[1] works[2]
0 3 7 5 3
1 1 5 5 3
2 1 5 5 3
3 0 4 5 3

알고리즘이 동작하는 과정을 편의상 t라고 했습니다. 

t=0은 과정 1의 정렬을 하는 과정입니다.

t=1은 works의 두번째 요소(works[1])까지의 요소들의 값들이 같도록 만드는 과정입니다. works[0]을  works[1]과 같도록 만들 수 있으므로 바꾸어주고 n에서 works[0]-works[1]을 빼줍니다. i가 2 이상이라면 i*(works[i-1]-works[i])를 빼주면 됩니다. 

t=2는 과정 2인데, 0이 아닌 요소가 3개인데, n은 1이므로 이 과정은 진행되지 않지만, 이해를 돕기위해 넣었습니다.

t=3은 과정 3으로, 남아있는 n을 앞에서부터 1씩 처리하는 과정입니다.

이제 t=3에서의 요소의 값들을 제곱하여 반환하면 됩니다.

 

* 시간복잡도는 최악의 경우 for문 3번으로 끝나므로, works의 길이를 N이라 하면 O(NlonN + N)이 됩니다(정확히는 O(NlonN + 3N)).

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def solution(n, works):
    if sum(works) <=n: return 0
    works.sort(reverse=True)
    
    equal = len(works)
    for i in range(1,len(works)):
        d = works[i-1]-works[i]
        if d==0:
            continue
        elif d*i<=n:
            for j in range(i):
                works[j] = works[i]
                n-=d
        else :
            equal = i
            break
            
    # 다 똑같아졌다.
    assign = n//equal
    for i in range(equal):
        works[i] -= assign
        n-=assign
    for i in range(n):
        works[i]-=1
    return sum(x**2 for x in works)
 cs

line 6의 for문이 과정 1(equal index까지 요소들의 값이 같게 됩니다.),

line 19이 n을 공평하게 처리하는 부분,

line 23이 남은 n을 1씩 앞에서부터 처리하는 부분입니다.

 

문제링크

 

코딩테스트 연습 - 야근 지수 | 프로그래머스

회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요. 제한 사항 works는 길이

programmers.co.kr

 

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

프로그래머스 SQL 중성화 여부 확인하기  (0) 2020.03.23
프로그래머스 Lv2 압축  (0) 2020.03.22
프로그래머스 Lv3 타일 장식물  (0) 2020.03.22
프로그래머스 Lv3 N-Queen  (0) 2020.03.22
프로그래머스 Lv3 베스트앨범  (0) 2020.03.20
반응형

유형 : dp

 

첫번째 오답

 동전들의 가치가 1, 2, 5로 주어지는 경우를 예로들면, 단순히 가치 i를 만드는 경우의 수 dp[i] = dp[i-1]+dp[i-2]+dp[i-5] 로 만드는 경우에는, 중복된 경우를 따로 카운트하게 되어 오답이 된다. 예를들면 i=3 인 경우를 예로 들면, dp[2]+dp[1]이 되는데, dp[2]를 사용하는 경우를 살펴보면, dp[2]는 1을 두개 쓴 경우와 2를 한개 쓴 경우 해서 2가지가 되고, 여기에 1을 한개 더 사용하여 3을 만드는 경우이므로 총 2가지 (1을 3개), (1을 1개, 2를 1개)가 된다. dp[1]은 1을 한개 사용하는 경우 한가지가 존재하고, 여기에 2를 한 개 사용하여 3을 만드는 경우가 되므로, (1을 1개, 2를 1개) 한가지가 된다. 따라서 dp[3] = 3 이라고 계산하게 되는데, 위의 세가지를 살펴보면 (1을 1개, 2를 1개) 가 두번 세어진 것을 알 수 있다. 즉, 1을 먼저 쓰고 2를 쓴 경우와, 2를 먼저 쓰고 1을 쓴 경우를 다르게 체크하는 것이다.

 따라서 이러한 중복되는 경우의 수를 피하기 위해 아래에서는 n 종류의 동전만을 사용하는 경우를 나누어서 계산하게 된다.

 

풀이 및 두번째 오답

 먼저 dp를 n x k+1 사이즈의 리스트로 선언한다. dp[n][k]는 첫 n+1개의 코인(0부터 세니까)을 사용하여 가치 k를 만드는 경우의 수이다. dp[0]의 경우에는 첫번째 동전만을 사용하는 경우이므로, dp[0]의 경우,

[1]+[1 if i%coin[0]==0 else 0 for i in range(1,k+1)] 로 초기화 해준다. 즉, k가 coin[0]으로 나누어지는 경우에만 가치 k를 첫번째 코인만으로 만들수 있다. 그 후의 점화식은 아래와 같다.

$dp[i][j]=\begin{cases}dp[i-1][j], & \mbox{if j < coin[i]} \\ dp[i][j-coin[i]]+dp[i-1][j], & otherwise\end{cases}$

 첫 경우는, 만드려는 가치 j가 i번째 코인의 가치보다 작은 경우로, 이러한 경우에는 i번째 코인을 사용할 수 없으므로, 전의 것을 그냥 사용하면 된다. 두번째 경우에서 dp[i][j-coin[i]]는 i번째 코인도 사용해서 가치 j-coin[i]를 만든 후에 i번째 코인을 사용하는 경우이고, dp[i-1][j]의 경우에는 i번째 코인을 사용하지 않는 경우가 된다. 이렇게 계산하면 위의 오답의 예를 다시 살펴보면 dp[1][3] (첫번째, 두번째 코인을 사용하여 가치 3을 만드는 경우의 수)는 dp[1][1] + dp[0][3] 이 된다. dp[1][1]의 경우에는 dp[0][1]로 주어지므로, 1이 되고, dp[0][3] 역시 1이므로, 위와 같이 중복된 경우는 세지 않을 수 있다. 

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import sys
n, k = map(int,sys.stdin.readline().split())
 
coin=[]
for _ in range(n):
    c = int(sys.stdin.readline())
    if c <=k:coin.append(c)
n=len(coin)
 
dp = [[1]+[1 if i%coin[0]==0 else 0 for i in range(1,k+1)]]+[[1]+[0 for i in range(1,k+1)] for j in range(1,n)]
for i in range(1,n):
    for j in range(coin[i]):
        dp[i][j] = dp[i-1][j]
    for j in range(coin[i],k+1):
        dp[i][j] += dp[i][j-coin[i]]+dp[i-1][j]
print(dp[n-1][k])
 cs

코드로 나타내면 다음과 같은데, 문제는 dp의 공간 복잡도가 $O(n\dots k)$가 되어 메모리 초과가 된다.

 

공간복잡도 줄이기

 그런데, 위의 코드를 살펴보면 실질적으로 dp[i][j]를 계산하는 13, 15 line에서 dp[i-1][j]가 계속 반복되는 것을 볼 수 있다. 즉, dp를 길이 k+1인 리스트로 선언한 후 15번째 줄의 우항의 마지막 항을 버리면 된다.

 

Python Code

1
2
3
4
5
6
7
dp = [1]+[1 if i%coin[0]==0 else 0 for i in range(1,k+1)]
 
for i in range(1,n):
    for j in range(coin[i],k+1):
       dp[j] += dp[j-coin[i]]
 
print(dp[-1])
 cs

 

문제링크

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 1890 점프  (0) 2020.03.09
백준 17478 재귀함수가 뭔가요?  (0) 2020.03.08
백준 1038 감소하는 수  (0) 2020.02.28
백준 2157 여행  (0) 2020.02.27
백준 2579 계단 오르기  (0) 2020.02.27
반응형

유형 : dp라고 쓰여있지만 완전탐색...

 

문제풀이

 10,21,321 처럼 큰 자리의 숫자가 작은 자리의 숫자보다 큰 숫자를 구하는 문제로, 결국 [0,1,2,3,4,5,6,7,8,9] 만들 수 있는 모든 subset을 구하는 문제와 동일하다.

 무슨 말인가 하니, 위의 0 ~ 9 숫자 중 중복되지 않는 n개의 숫자를 뽑으면 그 숫자들로 만들 수 있는 감소하는 숫자는 1개밖에 존재하지 않는다. 예를 들어 1,3,5를 골랐다면 531 이외의 가능한 감소하는 수는 없다. 따라서 1 ~ 9로 만들수 있는 감소하는 수의 총개수는 $2^{10} -1$ 개가 되는데, 그 이유는 0 ~ 9 총 10개의 숫자 모두 선택한다, 안 한다 두 개의 경우가 존재하기 때문이다. 따라서 입력값 n이 1024 이상인 경우에는 -1을 반환하면 된다(실제 구현할 때는 0부터 셈으로 1023 이상). 1023 이하인 경우에는, 10개의 숫자 중 뽑는 n개의 숫자를 1개부터 10개까지 늘리며 모든 가능한 조합으로 숫자를 만든 후, 정렬하여 n번째 수를 반환하면 된다.

 

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import sys
sys.setrecursionlimit(1000000)
global num
num = [9,8,7,6,5,4,3,2,1,0]
 
digit = 2
temp = [0 for i in range(2)]
global ans
ans =[]
i=0
def dfs(arr,digit,depth):
    global num
    global ans
    if depth == digit:
        t=0
        while digit>0:
            t+=arr[len(arr)-digit]*10**(digit-1)
            digit-=1
        ans.append(t)
        return
    for i in range(num.index(arr[depth-1])+1,10-(digit-depth)+1):
        arr[depth]=num[i]
        dfs(arr.copy(),digit,depth+1)
 
n = int(input())
if n >= 1023:
    print(-1)
else:
    for digit in range(1,11):
        arr = [0 for i in range(digit)]
        for i in range(10-digit+1):
            arr[0]=num[i]
            dfs(arr,digit,1)
        if len(ans) >= n+1:
            break
    ans.sort()
    print(ans[n])
 cs

21 line 은, depth번째 수 i 로 가능한 것들의 조건인데, i는 depth-1보다는 작아야 하고, 앞으로 digit-depth 만큼의 수를 더 뽑아야 하기 때문에, 뒤에 digit-depth만큼의 수는 남겨두어야 한다.

29 line의 digit이 위에서 말한 n(몇 개를 선택할 것인지로 몇 자릿수의 숫자를 만들지를 의미)이다.

 

문제 링크

 

1038번: 감소하는 수

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

www.acmicpc.net

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 17478 재귀함수가 뭔가요?  (0) 2020.03.08
백준 2293 동전 1  (0) 2020.03.01
백준 2157 여행  (0) 2020.02.27
백준 2579 계단 오르기  (0) 2020.02.27
백준 4949 균형잡힌 세상  (0) 2020.02.25

+ Recent posts

티스토리툴바