개발조아

문제 링크 : https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 접근법을 모르겠어서 알고리즘을 찾아보고 푼 문제이다. 핵심은 투포인터를 이용하는 것이다. 배열의 숫자 리스트를 정렬해서 따로 만들고 투포인터로 최소, 최대값을 결정하고 BFS 실행 후 조정해간다. BFS를 실행할때 시작점과 그리고 중간에 들르는 점들에 대해서 이전에 정한 최소, 최대값 범위에 포함되는지 체크해야한다. 모든 점이 범위를 통과하고 목표점에 도달했다..

문제 링크 : https://www.acmicpc.net/problem/15971 15971번: 두 로봇 입력에서 두 번째 줄에 주어지는 방번호는 1과 2, 세 번째 줄에 주어지는 방 번호는 2와 3, …, i번째 줄에 주어지는 방 번호는 i-1과 i, …, N번째 줄에 주어지는 방 번호는 N-1과 N이다 (아래 입력과 www.acmicpc.net 문제는 그냥 BFS 문제이다. 두 로봇이 통신하기 위해선 이웃한 두점으로 로봇이 이동해야한다. 이때 드는 비용의 최솟값을 구해야한다. 한가지 주의할 점은 두 로봇이 같은 위치에 있을 수 있다는 것이다. 이부분을 체크해줘야한다. 처음에는 BFS를 두번 돌렸다. 그래서 한 로봇에서 BFS를 돌리면서 각 점까지의 최소값을 저장했다. 그리고 다른 로봇에서 BFS를 돌..

문제 링크 : https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 비트마스킹으로 해결한 문제이다. 예전에 풀었던건데 그때는 BFS+DFS로 풀었다. 이 방법은 느리다. 모든 시작점과 더러운칸에서 BFS를 진행하고 마지막에 DFS를 진행 했기 때문이다. 그때의 알고리즘은 아래 더보기를 누르면 된다. 더보기 시작점과 더러운칸에 0부터 번호를 매기고 start라는 배열에 번호를 저장했다. 그리고 start배열의 점에서 각각 BFS를 실행하여 각 점사이의 거리 최..

문제 풀이 : https://www.acmicpc.net/problem/18119 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 시간초과가 계속 나서 비트마스크로 겨우 푼 문제이다. 일단 word를 전처리해야한다. 알파벳을 0~26 비트로 처리하자 0번째 비트는 a의 등장 유무 1번째 비트는 b의 등장 유무 이런식으로 처리된다. word에 포함된 알파벳을 비트로 표현해서 저장한다. 모음의 경우 처리를 해주지 않았다. 입력이 o, x라 들어올 때 o가 1일 때는 x를 기억하고 있었음이 보장되고, o가 2일 ..

문제 링크 : https://www.acmicpc.net/problem/6987 6987번: 월드컵 월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부 www.acmicpc.net 브루트포스, 백트래킹 문제이다. 나는 연산자 끼워넣기랑 유사하게 풀었다. https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개..

문제링크 : https://www.acmicpc.net/problem/11067 11067번: 모노톤길 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 개수 T가 정수로 주어진다. 각 테스트 데이터의 첫 번째 줄에는 카페의 수 www.acmicpc.net 길의 좌표를 줬을 때 잘 나열해놓고 원하는 카페 번호를 출력하면 된다. 일단 입력받은 x,y좌표를 오름차순으로 일단 정렬했다. 이는 길이 오른쪽부터 왼쪽으로 향하기 때문이다. 그리고 x좌표에 대해서 똑같은 값을 가진 점들의 개수를 세서 저장했다. y좌표는 일단 오름차순으로 정렬되어 있다. 하지만 카페의 길이 현재 점에서 위로 갈수도 있고 아래로 갈수도 있다. 그리고 길은 수평, 수직방향..

문제 링크 : https://www.acmicpc.net/problem/8982 8982번: 수족관 1 입력의 첫 줄은 수족관의 경계에 있는 꼭짓점의 개수 N(1 ≤ N ≤ 5,000)이 주어진다. N은 짝수이다. 수족관의 경계는 항상 꼭짓점 (0, 0)부터 시작한다. 그리고 마지막 꼭짓점은 (A, 0)의 형태로 끝난 www.acmicpc.net 문제의 설명은 어렵지 않지만 생각을 좀 많이 한 문제이다. 문제의 핵심은 수족관에 깊이를 수정해가는 것이다. 한 구멍으로 물이 빠졌을 때의 수족관의 물의 빠진 양을 수정하는데 이를 모든 구멍에 대해서 실행해보는 것이다. 예를 들어 2번 구멍으로 먼저 물이 빠진다 했을 때 왼쪽 첫번째 파란 원의 물의 양은 3, 오른쪽 파란원도 3, 그 오른쪽은 2가 될 것이다. ..

문제 링크 : https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 치킨집을 m개를 고르고 각 집마다 가장 가까운 치킨집과의 거리를 계산해서 합의 최솟값을 구하는 문제이다. 조합으로 치킨집을 m개 고르고 집마다 치킨집과의 거리를 계산해서 최솟값을 구하면 된다. from sys import stdin from itertools import combinations input = stdin.readline n,m = map(int, ..