링크 : https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 소요시간: 11분 실패 설계하기(접근방법) 1. 입력받기 a,b,c 를 입력받는다 2. 구현하기 이 문제는 지수의 법칙과 나머지 분배법칙을 알고 있어야 한다 즉 (10 ^ 12) % c를 계산한다고 했을 때 (10 ^ 6 * 10 ^ 6) % c 를 할 수 있다 그리고 나머지 분배 법칙은 ((10 ^ 6 % c) * (10 ^ 6 % c )) % c를 할 수 있다 또한 (10 ^ 3 * 10 ^ 3 * 10 ^ 3 * 10 ^ 3 *) % c 와 ..
링크 : https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 소요시간: 15분 25초 설계하기(접근방법) 1. 입력받기 삼각형 배열을 입력받는다 2. 구현하기 다음 항은 이전 항의 같은 열과 이전 행의 이전 열 중 최대값을 더하면 된다 dp[i][j] += max(dp[i -1][j - 1], dp[i - 1][j]) 그리고 배열의 시작이나 끝일때만 예외처리를 해주면 된다 3. 출력하기 코드(출력) n = int(input()) dp = [0 for _ in range(n)] for i in range(n): dp..
링크 : https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 소요시간: 30분 실패 설계하기(접근방법) 1. 입력받기 rgb 배열을 입력받는다 2. 구현하기 그 다음 항의 최소합은 그 이전에 자기 자신 색깔을 제외한 나머지 두 색깔의 최소값 중 하나와 더한 값이다 이 것을 일반화 시키면 rgb[i][0] += min(rgb[i-1][1], rgb[i-1][2]) 와 같은 형태가 나온다 3. 출력하기 n-1 항의 최소값을 ..
링크 : https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 소요시간: 1시간 15분 + 반례 탐색 설계하기(접근방법) 1. 입력받기 배열의 크기, 남길 치킨집의 개수 배열을 입력받는다 2. 구현하기 조합의 경우의 수를 구할 것인데 백트래킹을 사용하여 시간초과를 방지할 것이다 일단 모든 마을에 대해서 모든 치킨집의 거리를 저장한다 즉 마을이 4개 치킨집이 3개라면 distance_list = [ [치킨거리, 치킨거리, 치..
링크 : https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 소요시간: 11분 53초 설계하기(접근방법) 1. 입력받기 n,m 과 수열을 입력받는다 2. 구현하기 같은 숫자를 여러번 골라도 되니 set을 통해서 리스트의 중복 원소를 없애준다 그 후 list를 sort() 해주어 수열이 순차적으로 출력되도록 조정해준다 그 다음 dfs 백트래킹을 통해서 수열을 더해나가는데 문제의 조건인 비내림차순 수열이어야 하기 때문에 이전 원소보다 크도록 ..
링크 : https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 소요시간: 25분 실패 설계하기(접근방법) 1. 입력받기 n, m 과 수열을 입력받는다 2. 구현하기 num_list 내의 원소만 순회하면서 순열을 만든다 같은 숫자가 2개인 경우 2개를 사용 가능하나 같은 수열은 입력 못하는 것이 이 문제의 포인트이다 처음에는 리스트내에 새로 추가될 리스트가 없으면 append하는 방식으로 처리하려고 했으나 만약 8개 인 경우 순열의 개수가 8!..
링크 : https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 소요시간: 5분 58초 설계하기(접근방법) 1. 입력받기 n,m 을 입력받는다 2. 구현하기 비내림차순 순열을 구하기 위해서는 이전의 수열을 저장해주어 dfs의 인자로 넘겨주어야 한다 숫자가 너무 커지면 인덱스 넘버 자체를 넘겨 시간을 줄여주는 것이 좋겠지만 시간 초과가 넉넉하기 때문에 모든 숫자를 순회하되, 이전 숫자보다 크거나 같은 값만 lst에 추가해준다 3. 출력하기..
링크 : https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 소요시간: 4분 35초 설계하기(접근방법) 1. 입력받기 n, m 과 수열을 입력받는다 2. 구현하기 이전의 백트래킹은 1 ~ n까지 순회하였다면 이번 문제는 주어진 리스트 자체를 순회하면 된다 for i in num_list로 순회해서 해당 순열만 ans에 append 한다 3. 출력하기 ans를 출력한다 코드(출력) n, m = map(int, input().split(..
