풀이 보관함

🔗문제 1525번: 퍼즐 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 🖍풀이 한칸이 비워져있는 퍼즐을 순서대로 정렬하기 위한 최소 이동 비용을 구하는 문제 빈칸을 기준으로 사방의 셀을 옮겨가며 BFS방식으로 풀 수 있다. 🚩 2차원 배열이 아니라 문자열로 표현 빈칸을 기준으로 사방의 셀을 이동한다면 당연히 2차원 배열을 생각할 수 있지만, 이 풀이에서는 일련의 문자열로 취급해서 풀어주었다. 문자열에서 n 번째에 있는 빈칸을 x, y로 표현하는 법 문자열로 된 퍼즐을 BFS에 활용하는 법 최소 이동횟수를 구해야하기 때문에 이미 형성된 퍼즐을 큐에 넣으면 안된다. map이나 set를 활..

🔗 문제 17140번: 이차원 배열과 연산 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 크기가 3×3 (초기 배열 크기 3) 인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다. R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다. C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수

🔗 문제 20056번: 마법사 상어와 파이어볼 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다. => 격자의 범위가 벗어나는 법은 없다. 5칸 짜리에서 8번칸 이동해야하면 3칸에 위치시키면 된다. ==> x%=N 🖍 풀이 간단하게 정리하면 이렇게 풀 수있다. while(K--) { // 1. 파이어볼의 동시 이동 // 2. 파이어볼 나누기 } 1...

🔗 문제 15683번: 감시 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8) 둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. CCTV의 최대 개수는 8개를 넘지 않는다. 🖍 풀이 문제를 보면 맵도 작고 CCTV 개수도 작기 떄문에 완전 탐색으로 풀어주었다. 소스를 보는게 빠를 듯하지만 설명을 해볼게요.. 현재..

🔗 문제 3190번: 뱀 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 🖍 풀이 종료 조건을 보면 map의 범위를 벗어나거나 뱀 자기 자신과 부딪히면 게임이 종료된다. 뱀의 길이가 변하면서 이동하는 건 간단하게 deque로 해결했다. 머리를 내밀 때 push_front(), 꼬리가 짧아지면 pop_back()으로 해결했다. 더불어 map에 EMPTY, APPLE, SNAKE 세 종류의 데이터를 저장해서 뱀의 유무를 판단해주었다. 너무 친절하게도 시간 오름차순으로 방향 전환이 되어서 queue에 넣고 방향 전환시간이..

🔗 문제 20055번: 컨베이어 벨트 위의 로봇 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 🖍 풀이 문제를 정리해보자. 컨베이어 벨트가 오른쪽으로 움직인다. 당연히 로봇의 위치도 함께 움직인다. 이때 나가는 위치에 도달하면 로봇을 버린다. 적재한 로봇은 올라온 순서가 있다. 이 순서대로 로봇을 한 칸 더 이동시킨다. 이동하려는 곳의 내구성이 1 미만이면 이동하지 않는다. 이동하려는 곳에 로봇이 있으면 이동하지 않는다. 로봇을 이동한 후 이동하려는 곳의 내구성을 -1 더한다. 이때 나가..

🔗 문제 14500번: 테트로미노 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 🖍 풀이 모든 위치에서 탐색을 한다. 내 위치를 포함한 주변 위치를 총 4개를 모은다. 이게 테트로미노다. DFS로 4개를 만들든 BFS로 만들든 아무튼 인접한 공간 4개를 모으면 된다. 어떤 모양으로 모였나 디버깅하면 알겠지만 ㅗ, ㅜ, ㅏ, ㅓ 모양으로 방문하는게 어렵다는걸 알게 될 거다. BFS로 하면 만들 수 있는 줄 알았는데 안되길래 따로 oh()라는 함수로 방문해 줬다. (저주받은 작명) BFS로 풀면 508ms이고 D..

🔗 문제 16234번: 인구 이동 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다..

🔗 문제 14888번: 연산자 끼워넣기 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 🖍 풀이 +) 1e9를 이용해 최대, 최소를 표현하는 방법을 배웠다. 완전 탐색으로 싹싹 뒤져보면 된다. 인자로 입력받은 연산자의 개수를 집어넣고 함수가 한번 호출될 때마다 각 연산자로 연산해준다. solve(1, A[0], add, sub, mult, div); 💾 소스 #include long long max=-1e9 , min = 1e9; int N = 0, A[1..

🔗 문제 2307번: 도로검문 2307번: 도로검문 그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸리 www.acmicpc.net 🖍 풀이 문제를 하나씩 뜯어보면 일단 범죄자의 도주 경로와 최소 비용을 구해야 한다. 경로는 양의 가중치가 있는 그래프로 주어진다. 시작 지점과 도착 지점이 주어진다. 두 조건을 보아 다익스트라 기법을 이용해야 한다는 감을 잡았다. 어려웠던 점 최대 지연을 위해서는 모든 도로를 다 빼는 건 시간 초과에다가 틀린 접근이다.( 당ㅇ연함) 도주 경로의 도로를 빼야한다는건 알았는데 어떻게 구현할지 모르겠어서 인터넷의 도움을 받았다. dijkst..