분류 전체보기
2482_색상환
https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net dp를 2차원배열로 설정해서 풀 수 있다. dp[i][j]라면 i개의 색중에서 j개의 색을 선택하는 것이다. dp를 채워나간다고 생각해보자. 만약 dp[i][j]를 채운다고 생각해보자. i번째 색이 새로 추가되었다면 그 색을 칠하는 경우와 안 칠하는 경우 2가지가 나올 것이다. 만약 색이 추가되었다면 i-1번째색은 칠할 수 없고, 이때 색을 칠한다면 j-1개를 구해야 하므로 i-2 개의 색으로 j-1개의 색을 칠하는 경..
11478_서로다른부분문자열의 개수
https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net set을 통해서 중복이 들어갈 수 없게 한 후, 이어지는 문자열들을 집어넣으면 된다. s = input() result = set() for i in range(len(s)): for j in range(i,len(s)): result.add(s[i:j+1]) print(len(result))
14425_문자열 집합
https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 단순하게 풀 수 있는 문제인데 리스트로 풀면 시간초과가 나는 문제였다... 새롭게 알게된 사실인데 list자료형의 삽입,탐색등의 시간복잡도는 O(n)이며 딕셔너리 set의 자료형은 O(1)이라서 많은 차이가 난다고 한다. 이를 잘 생각하고 풀어보는것도 괜찮은 것 같다. import sys input = sys.stdin.readline n,m = map(int,in..
17404_RGB거리2
https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net RGB거리 문제와 동일하지만 첫번째 집과 마지막집이 연결된 형태이다. 첫집과 마지막집의 색이 같아야 하지 않으므로 세 경우를 집어서 생각할 수 있다. 첫집을 R로 칠하고 dp를 채워나가 cost를 만든 것중 마지막집을 G,B로 칠한것중 최소비용 첫집을 G로 칠하고 dp를 채워나가 cost를 만든 것중 마지막집을 R,B로 칠한것중 최소비용 첫집을 B로 칠하고 dp를 채워..
2098_외판원순회 1
https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 해당문제를 풀기 위해선 비트마스크, dp , dfs 총 3가지의 알고리즘을 활용해서 풀 수 있다. 처음에 비트마스크와 dp만 가지고 풀어보려다가 많이 헤맸던 문제이다.. 먼저 dp는 2차원 dp로 선언을 한 후 dp[i][j]라면 i는 현재 도시의 위치, j는 현재까지 방문한 도시들을 기록한다. 이때 j를 비트마스크를 이용해서 기록한다. 즉, 현재 도시가 3이..
1311_할일정하기1
https://www.acmicpc.net/problem/1311 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net 상당히 어려운 문제였다... 처음에 2차원 배열을 dp로 두고 한줄씩 채우면 뭔가 될꺼 같은데 이전에 방문하지 않았던 점에서 가져오는게 너무 어려워서 머리를 헤매다가 인터넷에서 약간의 힌트를 발견했다. 만약 문제의 예제케이스처럼 3명이 있다면 결국 우리는 [ 1 1 1 ] 와같이 채우는게 목표이다. 그리고 이 과정에는 [ 0 0 1 ] [ 0 1 0 ] [ 0 1 1 ] [ 1 0 ..