링크 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 형태로 변환하여 중복을 제거한 뒤 그 길이를 출력했다.

링크 https://www.acmicpc.net/problem/14405 난이도(solved.ac 참고) 실버5 풀이 이 문제는 너무 쉬워서 포스팅을 할지 말지 고민을 좀 했는데, 내 나름대로 괜찮다고 느꼈던 테크닉을 적기 위해 포스팅한다. 문자열에서 어떤 문자의 빈도를 구하기 위해서는 6행과 같은 방법이 괜찮다고 생각했다. 해당하는 값을 전부 *로 replace를 해주면 들어간 횟수를 구할 수 있다. 이 문제 한정으로 얘기를 해 보면, "pi", "ka", "chu" 외의 문자가 들어갈 경우 무조건 NO를 출력해야 한다. 그래서 *로 전부 바꾼 a를 돌면서 *가 아닌 값이 하나라도 있다면 flag를 False로 바꾼 뒤, flag가 False면 NO를 출력하게끔 했다. 알고 나면 괜찮은 테크닉이지만 모..

링크 https://www.acmicpc.net/problem/1715 난이도(solved.ac 참고) 골드4 풀이 우선 예제에 대한 해석이 필요하다. 10 20 40 이라면 10 + 20을 하는 과정에서 횟수가 30만큼 증가되고, 이후에 30 + 40을 하는 과정에서 30에 70을 더해서 값이 100이 된다. 여기서는 heapq 모듈을 사용해서 a의 값을 줄이는 과정을 반복하고 있으므로 결국 리스트 a의 길이가 1이 되는 순간에 끝이 나야 한다. 근데 그 값은 최소가 되어야 한다. 이 경우라면 그냥 단순하게 작은 수들부터 비교를 한 뒤에 점차 큰 수와 그 비교값을 다시 비교하는 과정을 반복한다면 되겠다는 생각이 들었다. 그래서 최소힙이 가정되어있는 heapq에서 두 개의 값을 빼낸 다음(이 두개는 당연..

링크 https://www.acmicpc.net/problem/14916 난이도(solved.ac 참고) 실버5 풀이 5로 나눴을 때 나머지가 0이라면 i번째 값은 그냥 i를 5로 나눈 값이고, 나머지가 0이 아니라면 0이 될 때까지 2씩 빼주고 그만큼 count에 더해준다. 이제 나머지가 0이 된다면 5로 나눈 몫을 count에 더해주고 그 값을 배열에 지정해준다.

링크 https://www.acmicpc.net/problem/1325 난이도(solved.ac 참고) 실버2 풀이 시간제한이 매우 빡빡한 문제이다. Python 3으로는 웬만해서는 맞을 수가 없고 채점 현황을 봐도 대부분이 PyPy3으로 맞았다. 일반적인 BFS문제와 크게 다르지 않은데, bfs 함수의 리턴값을 가공하는 과정이 좀 달랐다. 1부터 n+1까지의 반복문에서 각각 bfs 함수를 실행하면 각 인덱스에서 해킹할 수 있는 컴퓨터의 수가 나온다. 결과가 들어갈 result_list에는 가장 큰 값들만 들어가야하므로 거르는 과정을 거쳤다.

링크 https://www.acmicpc.net/problem/16953 난이도(solved.ac 참고) 실버1 풀이 숨바꼭질과 매우 유사한 문제이다. 그렇지만 숨바꼭질과 똑같이 풀면 메모리 초과가 뜬다. 범위가 10^9까지로 훨씬 넓기 때문이다. 그래서 count를 사용해야되는데, count를 그냥 변수로 처리하고 더해주는 방식으로 간다면 2배, 뒤에 1 붙인 모든 값에 대해 count가 더해지기 때문에 정확한 값을 도출할 수도 없다. 그래서 덱에 넣는 값에 count도 같이 넣었다. 그러면 몇 번째 연산인지 count로 구할 수 있다. x에 대해 두배한 값, 또는 뒤에 1을 붙인 값이 b를 넘지만 않는다면 전부 큐에 넣어주고 반복하다가 x가 b와 같아진다면 그 x에 대한 count를 반환하면 된다.