solved.ac의 Class 4 문제 중 곱셈 문제이다. 자연수 A를 B번 곱한 수를 C로 나눈 나머지를 구하는 문제이다. 여기서 생각을 해야 하는 것은 그냥 (A^B)% C를 구했다가는 시간 초과가 발생한다는 점이다.그렇다면 어떻게 구해야 하는가? 모듈러 산술 연산의 특징 (a * b) % c = (a % c * b % c) % c을 이용해 구해볼 것이다. 예를 들어 A^6인 경우,A^6 = A^3 * A^3으로 나누고,A^3 = A ^1 *  A^1  *  A로 또 나누어 구한다.즉, 재귀의 방식으로 구할 것이다. 문제를 풀 때, 참고했던 블로그는 아래와 같다.https://st-lab.tistory.com/237 [백준] 1629번 : 곱셈 - JAVA [자바]www.acmicpc.net/prob..

solved.ac의 Class 4 문제 중 RGB거리 문제이다.문제 조건 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구하는 문제이다.1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1) 번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.이전 집의 색과 현재 집의 색은 같으면 안 되므로 R, G, B로 경우를 나누어 계산해야 한다.즉, 현재 집과 같은 색을 제외한 값들의 최솟값과 현재 자신의 값을 더하면 된다.  해결했던 코드는 다음과 같다.  import sysif __name__ ..

solved.ac의 Class 4 문제 중 A → B 문제이다.문제 조건정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.2를 곱한다.1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최솟값을 구하는 문제이다.dfs를 사용하되, 인자로 현재 계산값과 연산의 횟수를 인수로 가지고 있어야 한다고 생각하고 문제를 풀었다.즉, (2를 곱한 값과 현재 연산 횟수+1)와, (10를 곱하고 +1 한 값과 현재 연산 횟수+1)을 인수로 주면서 각각 재귀함수를 하면 된다고 생각하고 문제를 풀었다.  해결했던 코드는 다음과 같다. import sysglobal a, bresult = []def dfs(n, cnt): # n의 값이 b보다 커졌을 경우는 더 이상 진행 X ..

solved.ac의 Class 4 문제 중 N과 M(4) 문제이다.1부터 비내림차순으로 내려가야 하는 특징 때문에 재귀 DFS 문제라는 것을 알 수 있다."한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다." 라는 주의사항이 있으니 조심하자. 해결했던 코드는 다음과 같다.import sysglobal n, mnumbers = []lst = []visited = []def dfs(): before = 0 if len(lst) == m: print(*lst) return for i in range(n): if before != numbers[i] and not v..

solved.ac의 Class 4 문제 중 N과 M(5) 문제이다. 주어진 숫자들을 정렬한 리스트를 재귀 백트래킹하는 문제라는 것을 알 수 있다." 수열은 사전 순으로 증가하는 순서로 출력해야 한다. "이라는 문제의 특징이 있으니 조심하자. 해결했던 코드는 다음과 같다.import sysglobal n, mnumbers = []lst = []def backtracking(d): # d가 m과 같아지면 return if d == m: print(" ".join(map(str, lst))) return for i in range(n): if numbers[i] in lst: continue; lst.append(numbers[i]) ..

solved.ac의 Class 4 문제 중 N과 M(2) 문제이다. 1부터 비내림차순으로 내려가야 하는 특징 때문에 재귀 DFS 문제라는 것을 알 수 있다."1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열"이라는 문제의 특징이 있으니 조심하자. 해결했던 코드는 다음과 같다. import sysglobal n, mlst = []def dfs(num): # 리스트의 개수가 m과 같아지면 return if len(lst) == m: print(" ".join(map(str, lst))) return for i in range(num+1, n+1): lst.append(i) dfs(i) lst.pop()if __name__ ..

solved.ac의 Class 4 문제 중 N과 M(4) 문제이다.  1부터 비내림차순으로 내려가야 하는 특징 때문에 재귀 DFS 문제라는 것을 알 수 있다."같은 수를 여러 번 골라도 된다."라는 문제의 특징이 있으니 조심하자. 해결했던 코드는 다음과 같다.import sysglobal n, mlst = []def dfs(num): # 리스트의 개수가 m과 같아지면 return if len(lst) == m: print(" ".join(map(str, lst))) return for i in range(num, n+1): lst.append(i) dfs(i) lst.pop()if __name__ == "__main__..