→

문제link: https://www.acmicpc.net/problem/117262xn 크기 직사각형을 1x2, 2x1 크기 타일로 채우는 경우의 수를 구해 10007로 나누었을 때의 나머지를 출력하는 문제이다. 접근%10007을 출력해야 한다는 사실을 꼭 유념해야 한다!(중요해서 위에 씀) 전에 푼 백준 9095번 문제와 비슷하다고 느꼈다. (https://going-on.tistory.com/43) 동일하게 이전 항의 값을 이용해 n일 때의 값을 구할 수 있다. [백준] 9095 | 1, 2, 3 더하기 [파이썬/python]문제link: https://www.acmicpc.net/problem/9095주어진 정수를 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제이다. 접근방법을 구할 때, ..

문제link: https://www.acmicpc.net/problem/9461문제에서 제시한 그림과 같이 정삼각형이 추가될 때, n번째 정삼각형 변의 길이 P(n)을 찾는 문제이다. 접근문제에서 삼각형은 나선에서 가장 긴 변에 추가된다.P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9인데, 여기에서 P(n) = P(n-2)+P(n-3)인 것을 알 수 있다.리스트에 미리 값을 저장한 후 알맞게 출력해주었다. 코드import sysinput = sys.stdin.readlineP = [0, 1, 1, 1] + [0] * 97for i in range(4, 101): P[i] = P[i-3] + P[i-2] for _ in range(int(input..

문제link: https://www.acmicpc.net/problem/9375해빈이가 가진 의상 목록을 입력받아 가능한 옷 조합의 가짓수를 출력하는 문제이다.같은 종류의 의상은 동시에 착용할 수 없고, 의상은 한 종류 이상만 착용하면(알몸이 아니기만 하면) 상관없다. 접근의상 종류별로 개수를 카운트한 후 곱해서 가능한 경우의 수를 계산했다. 이때, 해당 종류의 옷을 입지 않는 경우도 고려 가능하도록 종류별로 개수를 셀 때 +1 해주었다. 아무 옷도 입지 않은 경우는 제외해야 하므로 모두 곱한 값에서 1을 빼 출력하도록 했다. 코드import sysinput = sys.stdin.readlinefor _ in range(int(input())): clothes = dict() for __ in..

문제link: https://www.acmicpc.net/problem/9095주어진 정수를 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제이다. 접근방법을 구할 때, 수의 순서를 고려하는 것을 유념해야 한다. (1+2, 2+1을 별개로 본다.)가짓수를 세다 보면 규칙을 발견할 수 있다.f(n)이 n을 만들기 위한 방법의 수라고 할 때,f(n) = f(n-3) + f(n-2) + f(n-1)이 된다.이 문제에서는 n의 합을 구하기 위해 숫자 1, 2, 3만 사용한다.n의 합은 ((n-3)의 합 +3) + ((n-2)의 합 +2) + ((n-1)의 합 +1)과 같다.따라서 f(n-3) + f(n-2) + f(n-1) = f(n)이 된다. 코드import sysinput = sys.stdin.rea..

문제link: https://www.acmicpc.net/problem/2606연결된 컴퓨터의 번호 쌍을 입력받아, 바이러스에 감염된 컴퓨터의 수를 구하는 문제이다. 접근컴퓨터 번호 쌍을 입력받아 저장한다. 1번 컴퓨터에서부터 바이러스가 퍼져나가므로 1번 컴퓨터와 연결된 컴퓨터를 확인해 개수를 세어 출력하도록 했다.DFS를 활용했고, 한번 방문한 노드는 재방문하지 않도록 했다. 코드import sysinput = sys.stdin.readlinedef check(n): visited[n] = 1 for c in computers[n]: if not visited[c]: check(c)N = int(input())computers = [[] for _ in..

문제link: https://www.acmicpc.net/problem/2579계단을 오르면서 얻을 수 있는 점수의 최댓값을 구하는 문제이다. 접근DP를 이용해 문제를 풀었다.계단마다 점수가 있고, 계단을 오르며 점수를 획득할 수 있다. 계단은 한번에 한 칸 또는 두 칸을 오를 수 있으며, 연속으로 세 칸을 밟을 수는 없다. 마지막 계단은 꼭 밟아야 한다.마지막 계단에 꼭 도달해야 하므로, '이 계단에 도달하기 전에 어떤 계단을 밟았을까?' 시점에서 문제를 풀면 금방 점화식을 찾을 수 있다. 처음에 시작점이 첫 번째 계단인 것으로 잘못 이해해 틀린 답을 한 번 제출했다 ㅎㅎ; 시작점->첫 번째 계단->두 번째 계단->... 이다! 코드import sysinput = sys.stdin.readlineN =..

문제link: https://www.acmicpc.net/problem/1003주어진 함수의 특정 행이 몇 번 호출되는지를 구하는 문제이다. 접근문제에서 주어지는 함수는 피보나치 수열을 구하는 재귀 함수로, fibnacci(0)이면 "0", fibonacci(1)이면 "1"을 출력하게 되어 있다.0과 1이 출력되는 수를 각각 구해야 하는데, 이 0과 1이 출력되는 횟수 또한 규칙적으로 증가한다.함수 fibonaccci(n)의 n이 0, 1, 2, 3, ...일 때,"0"은 1, 0, 1, 1, 2, 3, 5, 8, 13, 21...,"1"은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34... 순으로 증가한다.따라서 피보나치 수열을 미리 구해 리스트에 저장한 후, 입력값에 따라 알맞은 출력 횟수..

문제link: https://www.acmicpc.net/problem/17219사이트 주소에 맞는 비밀번호를 출력하는 문제이다. 접근사이트 주소와 비밀번호를 딕셔너리에 저장하여 문제를 해결했다. 코드import sysinput = sys.stdin.readlineN, M = map(int, input().split())d = dict()for _ in range(N): url, pw = input().strip().split() d[url] = pwfor _ in range(M): print(d[input().strip()])

문제link: https://www.acmicpc.net/problem/11399N명의 사람이 한 줄로 서서 ATM을 이용한다고 할 때, 돈을 인출하는 데 걸리는 시간 합의 최솟값을 계산하는 문제이다. 접근한 사람이 ATM을 이용하고 있으면 그 시간동안 다음 사람들은 당연히 대기하게 된다. 시간이 적게 걸리는 순으로 돈을 인출하는 경우에 시간 합이 최솟값이 되므로 시간 순으로 정렬하여 계산했다.첫 번째 사람이 돈을 인출하는 시간은 모든 사람이 함께 소모한다. 하지만 마지막 사람이 돈을 인출하는 시간은 마지막 사람 혼자만 소모한다. 따라서 첫 번째 사람의 시간 P1에는 *N, ..., 마지막 사람의 시간 Pn에는 *1한 후 모두 더해 주었다. 코드N = int(input())P = sorted(map(in..

문제link: https://www.acmicpc.net/problem/18741부터 n까지의 숫자를 스택에 push, pop할 때 주어진 수열이 만들어질 수 있는지를 확인하는 문제이다. 접근오름차순으로 숫자를 스택에 push하면서, 입력받은 수열의 j번째 인덱스와 값이 같으면 pop하고, j를 증가시킨다. 코드import sysinput = sys.stdin.readlinen = int(input())a = [int(input()) for _ in range(n)]b = []ans = []i, j = 0, 0while i