꺼진불도다시보자

문제 https://www.acmicpc.net/problem/1913 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 접근방법 문제 풀이 과정은 다음과 같다. 1. N^2부터 계속 숫자를 감소시킨다. 2. 방향 변수를 두어 방향을 컨트롤 한다. 3. k변수를 두어서 끝 지점을 정하고 가는 방향의 끝에 도달하면 방향을 바꾼다. 추가로, 나는 벽에 끝에 도달했을 경우를 변수로 판별했는데, 이걸 2차원 배열에서 방향을 바꿀 곳을 true로 놓고 체크할 수도 있었다. 다시말하면, 이차원 배열을 만들고 꼭짓점에 1을 ..

문제 https://www.acmicpc.net/problem/10973 10973번: 이전 순열 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 접근방법 prev_permutation의 동작 원리를 묻는 문제였다. C++에서는 prev_permutation 함수가 있어서 쉽게 풀 수 있지만, 직접 구현해보기로 했다. 풀이 과정은 다음과 같다. 1. 뒤에서부터 탐색하며 바로 앞의 원소가 자신보다 큰 케이스를 찾는다. 2. 그런 원소가 존재한다면 그 원소를 기준으로 뒤에서 그 원소보다 작은 수 중 가장 큰 수와 swap한다. 3. 해당 원소가 원래 위치해있던 인덱스 뒤로 모두 내림차순 정렬한다..

문제 https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 접근방법 경우의 수를 줄여나간다는 생각은 했는데, 줄여나가는 방법에서 미스가 많았다. 10*10*10의 배열에 true false로 경우의 수를 체크했는데 이는 좋은 방법이 아니었다. 123부터 시작해서 987까지 1차원 배열에 담은 후에 숫자를 꺼내서, to_string을 이용해 각 자리의 수를 확인할 수 있는 방법이 있었다. 아쉽게도 이 방법을 생각하지 못했던게 패인인 거 같다. to_s..

문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 접근방법 문제 풀이 과정은 다음과 같다. 1. 치킨집 m개를 선정한다.('조합'을 이용해서) 2. 각 집마다 치킨 거리를 계산한 후 모두 더한다. 3. 그 중 가장 작은 값을 고른다. 문제 자체는 크게 어렵지 않아보였다. 시간이 관건이었다. 집의 좌표와 치킨집의 좌표를 각각 따로 vector에 저장해뒀다. 이 좌표들을 이용해서 구하면 graph 전체를 누비지 않아도 되서..

문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 접근방법 이 문제를 푸는 방법은 다음과 같다. 1. 벽 세 개를 설치한다. 2. 바이러스를 확산시킨다. 3. 안전영역의 크기를 구한다. 내가 가장 많이 고민했던 부분은 벽 세 개를 설치하는 방법이다. 벽 세 개를 설치한 후에 거기에 바이러스를 퍼뜨려야 하기 때문에, 벽을 세운 좌표에 visited표시를 해줘야하고, 다음 벽 세 개를 고르기 위해서 마지막으로 설치한 벽 세 개를 삭제하고 다시 설치해야한다...

문제 https://www.acmicpc.net/problem/1283 1283번: 단축키 지정 첫째 줄에 옵션의 개수 N(1 ≤ N ≤ 30)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄에 옵션을 나타내는 문자열이 입력되는데 하나의 옵션은 5개 이하의 단어로 표현되며, 각 단어 역시 10개 이하 www.acmicpc.net 접근방법 문자열 구현 문제였다. 검색안하고는 못 푸는 문제였다. getline 함수 사용법, string 조작하는 법. 다 몰라서 검색해서 알아봤다. 사용법은 다음과 같다. getline으로 문자열 받는 법 : getline([inputstream], [string], [char]) -> inputstream으로 stdin을 치니까 안되고 cin치니까 됐다. 아마 header가..

문제 https://www.acmicpc.net/problem/2564 2564번: 경비원 첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄 www.acmicpc.net 접근방법 처음엔 bfs문제로 풀 수 있을 거 같았다. 근데 입력값을 보고 테이블을 보니 bfs로 구현하기가 애매해보였다. 처음 시작점을 기준으로 떨어진 거리를 숫자로 표현할 수 있었다. 숫자를 계산하고, 동근이와 거리를 계산해주면 된다. 각 상점과 동근이 사이 최소 거리는 다음과 같이 계산한다. 1.동근이와의 거리를 계산한다. 2.총 거리에서 동근와의 거리를 뺀 거리를 계산한다. 3.둘 중 작은 ..

문제 https://www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net 접근방법 deque를 이용하면, index로 값을 찾을 수 있다. 값의 범위가 크지 않아서 돌릴 때마다 deque에서 값이 있나 찾아보고 없으면 넣고, 있으면 rec++해줬다. 코드 #include #include #include #include #include using namespace std; #define FOR(i, n) for(int i=0;i n >> m; vector ..

문제 https://www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 접근방법 단순하게 폭발할 폭탄 좌표를 기억했다가, 폭탄 'O'를 만나면 폭발하면 된다고 생각했다. 하지만, 간과했던 부분이 있었다. '모두' 한번에 폭발한다는 가정이다. 나는 대수롭지 않게 생각했다. 그냥 한 바퀴 loop돌리면서 폭탄 제거하면 당연히 '모두' 한번에 폭발한 것과 같은 효과를 낼 수 있을 것이라는 기대를 했다. 하지만 생각과는 달랐다. 예를 들어서 1번과 같은 다음 케이스의 경우 폭발하고 나서..

문제 https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 접근방법 n과 m 중 작은 값을 2로 나눈 값(min(n, m) / 2)만큼 for문을 돌렸다. loop 안에서 각각의 회전의 while문 4개로 구현했다. 코드 int n, m, r; vector table; void Rotate() { int bn = n, bm = m; for (int i, j..