링크 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 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는..

링크 https://www.acmicpc.net/problem/14503 난이도(solved.ac 참고) 골드5 문제 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음과 같이 작동한다. 현재 위치를 청소한다. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다. 왼쪽 방향에..

링크 https://www.acmicpc.net/problem/15686 난이도(solved.ac 참고) 골드5 문제 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 임의의 두 칸 (r1..

N과 M 여러 문제를 한꺼번에 포스팅한다. 쓰이는 툴들이 거의 비슷하다. 링크 N과 M(1) https://www.acmicpc.net/problem/15649 N과 M(2) https://www.acmicpc.net/problem/15650 N과 M(3) https://www.acmicpc.net/problem/15651 N과 M(4) https://www.acmicpc.net/problem/15652 N과 M(5) https://www.acmicpc.net/problem/15654 난이도(solved.ac 참고) 5개 전부 실버3 풀이 (1) N과 M(1) 1번 문제는 단순 순열 문제였다. 단지 하나가 있을 때는 i[0]만 출력하게 함으로써 에러를 방지해야 했다. (2) N과 M(2) 2번 문제는 단..

바로 이전 포스팅의 문제를 풀면서 맞닥뜨린 에러에 대해 앞으로도 계속 검색하면서 찾을 것 같아서 그냥 여기에 적어둔다. int_list = [1, 2, 3, 4, 5, 6, 7] result = ''.join(int_list) # TypeError: sequence item 0: expected str instance, int found int형의 list를 join하려고 보면 이러한 에러가 생긴다. 뜻을 해석하자면 join할 때는 string이 들어가야 하나 int가 들어갔다는 것이다. 이것을 join하고 싶다면 어떻게 해야 할까? int_list = [1, 2, 3, 4, 5, 6, 7] result = ''.join(map(str, int_list)) result_to_int = int(''.joi..

링크 https://www.acmicpc.net/problem/5568 난이도(solved.ac 참고) 실버5 풀이 permutations를 사용하면 쉽게 풀 수 있는 문제이다. card_list 중 pick개를 순서대로 뽑아서 줄세우기를 한 뒤에, 그 요소들을 join을 이용해서 합친 요소를 result_list에 넣었다. 문제에 나와있는 것처럼 2113의 경우라도 두 가지 이상이 존재할 수 있으므로 집합 자료형인 set 형태로 변환하여 중복을 제거한 뒤 그 길이를 출력했다.