haeguri

동전 문제

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

첫 번째 시도

동적 프로그래밍으로 풀고 싶었다.
동전의 개수 N = 2, 동전의 종류 C = [1,2], 만들어야 할 금액 M = 1000가 입력된다고 하고.

D[1]은 가능한 모든 동전을 사용해 1원을 만들 수 있는 경우의 수
D[2]은 가능한 모든 동전을 사용해 2원을 만들 수 있는 경우의 수
….
D[M]은 가능한 모든 동전을 사용해 M원을 만들 수 있는 경우의 수

여기서 D[M]을 구하는 일반화된 식을 만들어보려고 M=1인 경우부터 쭉 나열했다.

이런식으로 표를 작성했는데, 경우의 수가 중복해서 계산되는 문제가 있었다.

두 번째 시도

이상한 표만 계속 그리다가 결국 구글링..

http://blog.naver.com/occidere/220793012348 이 글이 가장 도움이 됐다. 코드는 안보고(!) 일반화하는 방법을 참고했다.

동전의 종류가 오름차순으로 주어지는 것에 가장 큰 힌트가 있었다.
동전 1, 2가 있다면

1. 동전 1원으로, 1원부터 M원까지 만드는 경우의 수를 구하고, 결과를 D[M]에 저장.
   

   

   
   

2. 동전 1원과 2원으로, 1원부터 M원을 만드는 경우의 수를 구한다. 앞 단계에서 구했던 D[M]을 재사용한다 !!
   

   

 한 마디로 앞 단계에서 사용 가능한 동전(1원)으로 M원을 만드는 경우의 수에, 현재 단계에서 새로 추가된 동전(2원)으로 M원을 만드는 경우의 수를 더한다.

최종 코드

T = int(input())

for _ in range(T):
    N = int(input())
    C = list(map(int, input().split()))
    M = int(input())

    d = [0 for _ in range(M + 1)]

    d[0] = 1

    for coin in C:
        for m in range(coin, M + 1):
            d[m] = d[m] + d[m - coin]

    print(d.pop())

Authentication

Authentication은 당신이 누군지 확인한다. 예를 들어서 당신은 SSH 클라이언트를 이용해 Unix 서버에 로그인할 수 있거나,  POP3, MTP 클라이언트를 이용해 당신의 이메일 서버에 접근할 수 있다. 

Authorization

Authorization은 당신이 작업을 하도록 허가됐는지 확인한다. 예로 당신은 ssh 클라이언트를 경유해 Unix Server로 로그인하는 것이 허용될 수 있지만 당신은 디렉터리 혹은 어떤 다른 파일 시스템을 탐색하는 것도 허용되지 않는다.

Authorization은 성공적인 Authentication후에 일어난다.

출처 http://www.cyberciti.biz/faq/authentication-vs-authorization/