![]()
https://www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 두자릿수일수도 있고 한자릿수일수도 있다 이게 헷갈렸다 근데 이게 이 문제의 포인트 ! 단, 두자릿수는 10 ~ 26 이어야 한다. Z가 26이므로 마지막 알파벳이된다. 한자릿수는 0이면 안된다 !! A가 1부터 시작하기 때문이다 그리고 한자리수로 0보다 클때 : dp[i] += dp[i-1] 로 이전값을 더해준다 현재 검사중인 인덱스와 그다음 인덱스를 합쳐서 10이상 26이하의 두자릿수로 볼 수 있을 때 : 두자릿..
https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 완전탐색으로 풀었다 ! 파이썬에 조합 라이브러리 combinations가 있는데, 조합 라이브러리를 완전 탐색에 유용하게 쓸 수 있었다. N 명중 N//2를 뽑는 조합을 구했고 뽑은 N//2 명의 팀원들은 start 팀이라고 한다. 그리고 start 팀에 들어가지 않는 팀원들은 link 팀에 속하게 되는데, 이를 집합 set() 화 시켜서 차집합으로 구했다 ! 그러면 현재 총 6명이 있었다고 치면, start = (1..
permutations 를 써서 가능한 순열 조합들을 모두 확인해 보는 방법으로 풀었다. https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net # 10819 차이를 최대로 from itertools import permutations n = int(input()) array = list(map(int, input().split())) result = 0 cases = permutations(array, n) for case in cases: temp = 0 for..
![]()
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 트리도 결국 그래프에 속한다! 라고 생각하면 조금 더 쉽다 모양은 나무처럼 생겨서 이상하지만,, 결국 우리는 1번 노드에서 가장 멀리 떨어진 정점을 찾고, 그 정점에서 가장 멀리 떨어진 정점을 찾아서 두 가중치를 더해주면 최대값이 된다 이 예시에서도 1번에서 가장 떨어진 노드는 9번이다. 이말은 노드 1에서 출발 했을 때 가중치 값이 가장 큰 노드가 9라는 것이다 그후 9번을 ..
![]()
시뮬레이션 문제는 많~~~~~~~~~이 풀어봐야겠다 그나저나 청소년상어였던가 그것도 삼성기출인데 미세먼지 안녕이랑 비슷하게 빡 구현 (?) 이다. 난이도는 이게 그나마 아주조금 더 쉬운편 1. 먼지를 이동시킨다 다른 풀이를 참고했는데, 임의의 배열 공간(temp_array)을 만들어서, 그 배열을 이용해서 먼지를 상하좌우로 퍼뜨린것을 저장하고 원래의 배열로 옮기는 방법이다. 2. 공기청정기 가동 -> 위쪽 공기청정기의 x 좌표와 아래쪽 공기청정기 x 좌표를 경계로 전체 정사각형을 분할하여 생각한다. 그리고 벽면에 부딪힐 때 -> 즉 이동가능한 x, y 좌표의 범위를 벗어난 경우일 때, 방향을 차례대로 꺽어주면 된다 (반시계 방향 & 시계 방향) 칸은 원래 배열에 빈칸인 '0'을 앞쪽에서부터 삽입해서 나간..
1. 첫번째 시도.. 시간초과난다 from itertools import permutations n = list(input()) result = -1 cases = permutations(n, len(n)) for case in cases: if case[0] == '0': continue else: num = '' for i in case: num += i num = int(num) if num%30 == 0: result = max(result, num) print(result) if 문에서 30의 배수가 아닌 조건을 걸러주면 된다 !! 우선 30의 배수를 떠올려 보면 30, 60, 90, 120, 150, 180, 210 ... 0 으로 끝나는 것을 알 수 있다!! 또한 '3'의 배수의 성질인 각자..
![]()
우선 정말 단순하게 for문 이중으로 돌린 나의 코드 .. 날먹시도 실패 역시 시간초과 난다 # 11660 구간 합구하기 n, m = map(int, input().split()) graph = [] for _ in range(n): graph.append(list(map(int, input().split()))) for _ in range(m): x1, y1, x2, y2 = map(int, input().split()) result = 0 for i in range(x1-1, x2): for j in range(y1-1, y2): result += graph[i][j] print(result) DP로 풀어야 시간 초과가 나지 않는다. 그리고 파이썬 특성상, input() 대신 sys.stdin.rea..
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 각 노드들에서 x로 갈때 다익스트라 최단경로 알고리즘을 이용해 최단거리를 구하면 노드 i에서 모든 노드까지의 최단 거리 결과를 알 수 있다. 이 결과값을 나는 최단 거리를 저장하는 리스트 dist라고 두었다. dist[x]값이 바로 학생 i가 파티 주최지 x 노드까지 '가는' 데에 소요되는 최단경로 cost이다. 문제는 왕복을 해야 한다는 것인데, 원래는 구해놓은 최단거리에 2배 곱해주면 되지 않나라고..
