개발조아

문제 링크 : 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, ..

문제 링크 : https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 시뮬레이션 문제이다. 나는 큐를 이용하여 풀었다. 4방향 확인 중 이동할 곳이 있다면 현재 좌표를 수정한다. 만약 4방향 중 이동할 곳이 없다면 뒤로 이동하는데 벽이라면 답을 출력하고 끝내면 된다. from sys import stdin input = stdin.readline dx = [-1,0,1,0] dy = [0,1,0,-1] n,m = map(int, input().spl..

문제 링크 : https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 구현, 시뮬레이션 문제이다. 보통 이런 시뮬레이션 문제는 문제에서 하라는대로만 하면 잘맞긴했다. 근데 그게 어려울뿐... 문제는 톱니바퀴를 하나 회전했을 때 주변 톱니바퀴의 상태에 따라 같이 회전한다. 주어진 입력대로 다 회전후 모든 톱니바퀴의 상태에 따라 점수를 계산하라 이다. 회전을 시작하는 톱니바퀴는 좌우 톱니바퀴를 확인한다. 주변 톱니바퀴는 한쪽 방향만 확인하면 된다. f..