목록분류 전체보기 (123)
풀이 보관함
🔗 문제 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..
🔗 문제 1976번: 여행 가자 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 🖍 풀이 Union-Find로 간단히 풀 수 있는 문제였다. 여행가려는 지점(route)들이 같은 그래프에 속한다면 재방문을 하겠지만 아무튼 갈 수는 있다. 하지만 이어진 곳이 없는 아예 분리된 그래프라면 방문할 수 없다. 그래프 서로소 집합 구하기?.. 바로 유니온 파인드라는 생각이 들어 풀 수 있었다. 1. 연결된 지점을 받을 때마다 merge를 통해 한 그래프로 만들어준다. 한 그래프로 만든다는 건 부모 노드가 같으면 같은 ..
🔗 문제 22868번: 산책 (small) 22868번: 산책 (small) 첫 번째 줄에는 정점의 개수 $N$과 두 정점 사이를 잇는 도로의 개수 $M$이 공백으로 구분되어 주어진다. 두 번째 줄부터 $M + 1$ 번째 줄까지 정점 $A, B$가 공백으로 구분되어 주어진다. 정점 $A$와 www.acmicpc.net 🖍 풀이 다익스트라를 이용해서 최소 길이를 찾으려고 했다. 하지만 문제를 읽어보면 모든 간선간의 이동 비용은 1이므로 단순하게 BFS로 풀면 된다. 위 조건 덕분에 정렬 후에 가장 처음 만난 노드로 이동하는 것이 최소 비용이 된다. S → E까지의 최소 이동 비용을 구한다. E → S 까지 최소 이동 비용을 구한다. 1 + 2 의 비용 합산 비용으로 정답을 찾을 수 있다. BFS(S, E)..
🔗 문제 16918번: 봄버맨 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 🖍 풀이 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이 설치된 시간은 같다. 다음 1초 동안 봄버맨은 아무것도 하지 않는다. 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다. 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다. 3과 4를 반복한다. 폭탄 터지는 조건 설치 후 3초 후 터진다. 터질 때 상하좌우자리도 빈칸..
🔗 문제 https://www.acmicpc.net/problem/13019 13019번: A를 B로 첫째 줄에 A, 둘째 줄에 B가 주어진다. 두 문자열의 길이는 같으며, 길이는 50을 넘지 않는다. 또, 알파벳 대문자로만 이루어져 있다. www.acmicpc.net 🖍 풀이 solve() : A와 B의 구성요소 유무로 가능성 확인 A와 B의 문자열 길이가 같아야 한다. A와 B를 정렬했을 때 서로 같아야 한다. 같은 문자 구성이라면 정렬했을 때 똑같다! 문자열 길이가 짧아서 정렬해도 시간 초과 없음 solve2() A와 B 문자열을 뒤에서부터 같은지 확인하며 다른 문자열이 나오면 ++result 각 A, B의 뒤를 가르키는 포인터 aptr, bptr를 만들고 서로 같을 때까지 aptr을 왼쪽으로 이동..