import sys input = sys.stdin.readline arr = [] for _ in range(9): arr.append(list(map(int, input().rstrip()))) row = [[0]*10 for _ in range(10)] col = [[0]*10 for _ in range(10)] box = [[0]*10 for _ in range(10)] for i in range(9): for j in range(9): n = arr[i][j] row[i][n] = 1 col[j][n] = 1 box[i//3+j//3*3][n] = 1 def solve(cnt): if (cnt==81): for i in range(9): for j in range(9): print(arr[i][..
복습
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 두 팀으로 나누는 걸 어떻게 구현해야 할 지 감이 잘 오지 않았다. 1부터 N명의 선수가 있을 때, 그 선수가 a팀에 들어가는 경우와 b팀에 들어가는 경우 두 가지 이므로,, 그걸 이용해서 백트래킹으로 풀 수 있을 것이라 생각했다. 그런데 파이썬은 시간초과가 나왔고, pypy는 15프로 정도에서 틀렸다고 계속 떠서.. 일단 파이썬 조합 라이브러리를 이용해서 풀었다. 처음에는 심지어 N은 짝수이고 N/2명으로 나눈다는 ..
https://www.acmicpc.net/problem/20301 20301번: 반전 요세푸스 첫째 줄에 정수 $N$, $K$, $M$이 주어진다. ($1 \leq N \leq 5\ 000$, $1 \leq K, M \leq N$) www.acmicpc.net 큐를 이용해서 푸는 것이라는 건 알았는데, 하나하나 pop할 때마다 K를 더해서 체크하는 방식으로 풀어가지고 계속 시간초과가 났다. 다시보니 굳이 그렇게 하지 않고 한번에 K-1번 혹은 반대인 경우는 K번 이렇게 돌면서 pop을 해주면 되는 것이었다. 이 방식을 잘 기억해야겠다. import sys from collections import deque input = sys.stdin.readline N, K, M = map(int, input()..
https://www.acmicpc.net/problem/20923 20923번: 숫자 할리갈리 게임 첫째 줄에는 도도와 수연이가 가지는 카드의 개수 $N$($ 1 \leq N \leq 30\,000$)과 게임 진행 횟수 $M$($ 1 \leq M \leq 2\,500\,000$)이 주어진다. 둘째 줄부터 $N$개의 줄에는 띄어쓰기로 구분하여 도도와 수연 www.acmicpc.net 처음에 문제가 이해가 안되서 한참 보다가 질문에서 두 사람이 낸 카드의 총합이 M이라는 걸 보고 아.. 그제야 이해했다. 이해한 후에는 그렇게 어렵지 않았는데, 처음에 바보같이 그라운드의 카드를 종을 친 사람의 덱으로 가져올 때 그라운드를 스택이라고 생각하고 풀어서 시간초과가 났다. 아니 사실 pypy로 돌렸을 땐 틀렸습니다..
https://www.acmicpc.net/problem/3078 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 슬라이딩 윈도우를 활용한다고 하여도.. 같은 길이의 문자열을 찾으려면 K개의 범위를 다 돌아봐야 하니까 시간초과가 날 것 같은데... 하는 생각에 오래 고민하다가 슬라이딩 윈도우의 장점을 사용하기 위한 방법을 생각해보았다. 바로 문자열의 길이를 인덱스로 하는 배열을 따로 만든 후에 같은 길이의 문자가 윈도우 안에 있는경우 그걸 인덱스로 한 값을 +1 해주는 방식이었다. 이렇게 ..
https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 아... 정말 어려웠다... 사실 어려운 것보다 내가 너무 어렵게 생각했던 것 같다. 처음에는 주어진 입력을 각각 원소로 해서 2차 배열을 만들어 저장하고 maxHeight를 찾고 그걸 기준으로 어떻게 잘 나누어서 해보자.. 라고 접근을 했는데 이 방식도 계속 파고 들어가면 풀 수 있을 것 같긴 하나.. 이렇게 푸는 게 과연 맞는 건가 하는 의문이 계속 들었다. 그리고 나서는 아,..
https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 머리가 안돌아가서.. 도저히 풀 수 있는 방법이 생각나지를 않았다. 예시의 답이 1+1+2+3+6+7 = 20 보다 하나 더 큰 수라는 건 알았지만, 그리디를 이용해서 어떤 공식을 찾을 수 있을 지 생각이 나질 않았다. 그래서 질문을 좀 검색해 본 결과.. 현재 뽑은 숫자가 지금까지 더한 숫자 보다 작다면 그 수는 지금 까지의 더한 수(SUM) 부터 뽑은 수를 더한 값(SUM + ARR[i]) 까지 만들 수..
https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 처음엔 문제에 나와있는 코드를 그대로 구현해봤는데, 시간초과가 났다. 버블정렬은 O(n^2)의 시간복잡도를 가지기 때문이다. import sys N = int(sys.stdin.readline()) A = [-1] for _ in range(N): A.append(int(sys.stdin.readline())) for i in range(1, N+2): change = Fa..
https://www.acmicpc.net/problem/2155 2155번: 삼각형의 최단 경로 첫째 줄에 두 정수 A, B(1≤A, B≤1,000,000,000)가 주어진다. www.acmicpc.net 문제풀이: 어떻게 풀어야 하는 지 도무지 모르겠었는데..(사실 생각하기 귀찮아서 미뤄뒀던 걸수도..) 동아리 부원이 푼 걸 보고 힌트를 얻었다! 엄청난 삽질.. 까진 아니고 알고 나니 아.. 하는 그런 문제였다. 이렇게 푸는 게 정석일 지는 모르겠지만.. 루트 즉, 1번 위치부터 각 번호까지의 최단 경로를 구해보면 0 2 1 2 4 3 4 3 4 6 5 6 5 6 5 6 이렇게 나온다! 이 규칙은 쉽게 구할 수 있으니 이렇게 구해서 큰 수에서 작은 수를 빼주기만 하면 되는 것.. import sys ..
https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 문제풀이: 플로이드 와샬 알고리즘을 사용하여 문제를 풀었고, pypy로 통과했다. 플로이드 와샬 알고리즘을 사용해야겠다고 생각하는 게 어려운 것 같다. import sys V, E = map(int, sys.stdin.readline().split()) INF = 10**10 graph = [[INF]*(V+1) for _ in range(V+1)] for _ i..
