링크 https://www.acmicpc.net/problem/1850 난이도(solved.ac 참고) 실버2 풀이 input값 만큼의 1의 개수로 이뤄진 두 수의 최대공약수를 구하는 문제이다. 그냥 result에 '1'의 개수만큼 넣어서 구하면 메모리 초과가 뜬다. 그럴만도 한게 예제 입력 중에 500000000000000000이라는 매우 큰 수가 있기 때문. 저걸 다 구할 필요가 없다. 몇 자리 수인지만 알면 된다. 왜냐면 어차피 어떤 수든 간에 1로 바꿔준 수들이기 때문.. 일반적인 두 수의 최대 공약수를 구한 다음 그 갯수만큼 1로 바꿔주면 된다.

링크 https://www.acmicpc.net/problem/17352 난이도(solved.ac 참고) 골드5 풀이 input값을 받은 것들이 속하는 집합을 만든다. a와 b를 input으로 받았다면 각 a와 b의 루트 노드를 찾아서(find_parent 함수로) 더 작은 값이 부모 노드가 되는 방식이다. 현재 문제에서는 다리 하나만 놓으면 모든 노드가 전부 연결이 되어 있는 상태이다. 즉, n개의 섬 중 단 하나의 부모 노드만 다르다는 것이다. 그 값을 찾아서 (n-1개의 섬의 부모 노드, 나머지 하나의 섬의 부모 노드)의 값을 출력해주면 되는 문제였다. 이렇게 출력하면 되는 이유는, 부모 노드끼리 연결함으로써 최종적으로 모든 섬에 다 갈 수가 있게 되기 때문이다.

링크 https://www.acmicpc.net/problem/14502 난이도(solved.ac 참고) 골드5 풀이 1. input값으로 받은 a 리스트를 돌면서 값이 0이라면 전부 candidate라는 리스트에 인덱스 형태로 넣어주고(ex. (0, 1)), 2라면 큐에 담는다. 2. candidate 리스트에서 3개를 뽑아내는 순열 반복을 하면서 큐와 a를 각각 카피해서 새로운 변수에 지정해주고 그 순열에 해당하는 부분에 대해 a_copy 내의 해당 인덱스의 값을 1로 바꿔준다. (3개를 뽑아 벽을 세우는 것) 3. 그다음 result라는 변수에 bfs 함수의 리턴값을 부여한다. 3-1. bfs 함수에서는 a_copy 내의 값이 0일 경우 전부 2로 바꿔준 뒤 큐가 비게 되면 while문이 끝나면서 ..

1. 구간 합 구하기 4 https://www.acmicpc.net/problem/11659 난이도(solved.ac 기준): 실버3 풀이 간단한 DP 문제다. DP 배열 값은, 이전 인덱스의 값에 + 이전 인덱스의 input값으로 받은 리스트 값을 더해주면 된다. 구간을 더해준 뒤 dp[목적지점] - dp[시작지점-1] 을 해주면 해결할 수 있다. 이 부분은 직접 dp값을 출력해보는 게 더 와닿을 것이다. 여기에서 sys.stdin.readline을 사용하지 않으면 무조건 시간 초과가 난다. 따라서 sys.stdin.readline을 반드시 써야 한다. 2. 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 난이도(solved.ac 기준): 실버1 풀이 1번의 구간..

링크 https://www.acmicpc.net/problem/1912 난이도(solved.ac 참고) 실버2 풀이 가장 큰 값이 음수라면 일단 더해봤자 값이 더 커질 수가 없으므로 그 값만 출력한다. 그게 아닐 경우에는 dp라는 배열을 따로 만들어서 첫 값으로는 input값을 받아서 만든 리스트의 첫번째 값을 반환하고 그 이후부터는 dp의 이전 인덱스 값과 input값을 받아서 만든 리스트 a의 현재 인덱스 값을 더한 게 양수인 경우에만 dp의 현재 인덱스에 값을 부여해주고 그게 아니라면 dp[i]는 0으로 그대로 남게 된다. 즉 더한 값이 0보다 작을 경우엔 0으로 초기화하여 다시 시작하는 과정을 반복한 것이다.

링크 https://www.acmicpc.net/problem/3273 난이도(solved.ac 참고) 실버3 풀이 처음에 조합을 이용해서, aC2를 한 두 개의 합이 x일 경우 count를 +1 해줬는데, 그렇게 하니까 시간초과가 떴다. 그래서, sort 후에 투 포인터를 사용해서 합보다 작으면 last 값을 -1, 크면 first 값을 +1, 같으면 last값 감소와 first값 증가를 동시에 해줬다.

링크 https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 난이도(solved.ac 참고) 골드5 풀이 리스트로 주어진 값들에 대해 1부터 돌면서 (현재값 - 이전값)을 절댓값 처리한 값을 넣는다. 그리고 이 값들의 최소공약수를 구한다. 그 다음 이 최소공약수의 약수를 전부 출력하면 된다. 왜냐면 최대공약수로 나눴을 때 나머지가 같다는 것은 결국 최대공약수의 약수로 나눴을 때도 나머지가 같다는 뜻이기 때문이다. 이 문제는 두 가지 이유로 어려웠다. 1) 아이디어 생..

링크 https://www.acmicpc.net/problem/17129 난이도(solved.ac 참고) 골드5 풀이 일반적인 BFS문제중 하나이다. visited를 방문 여부와 + 그 지점까지의 거리를 구하는 용도로 사용했다. visited를 1부터 시작했기 때문에 실제로 답을 낼 때는 -1을 해줘야한다. 왜냐면 다음 지점을 방문할 때마다 1씩 증가하게 해야하는데 그러면 0부터 시작해야되지만 그렇게 하면 not visited[nx][ny]에 걸려서 25행의 if문을 통과할 수 있기 때문이다. 근데, PyPy로 제출했을 때는 통과했는데 Python으로 제출하니까 시간초과가 떴다. 대체 왜..? 하고 보니까, Python3으로 맞은 사람이 단 한명도 없었다. 이 문제 한정 PyPy만 통과할 수 있다는 점...

링크 https://www.acmicpc.net/problem/1759 난이도(solved.ac 참고) 골드5 문제 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다. 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다. 새 보..

링크 https://www.acmicpc.net/problem/3190 난이도(solved.ac 참고) 골드5 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는..