판교의 메타몽

문제 링크 : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 이 문제에서 핵심적으로 구현해야하는 요소는 다음 두 가지다. (1) 벽을 3개 세울 곳 (2) 바이러스가 다 퍼진 후 안전구역의 크기 처음에 벽을 3개 세울 곳을 고민하다보면 자연스럽게 '브루트 포스'가 떠오를텐데, 이렇게되면 시간 초과가 나지 않을까 고민하는 사람도 있을것이다. 하지만 이 문제는 브루트 포스를 활용해도 시간초과가 나지 않는다. 배열의 사이즈는 최대 8*8이기 때문이다. (1) ..

문제 링크 : https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 풀이는 다음과 같다. 1. 먼저 필요한 변수들을 선언해주고 값을 저장해준다. int n,m,t,p,pn,ans=0; bool ch[51]; // 진실을 아는지 여부 bool res[51]; // 과장된 이야기를 할 수 있는 파티 여부 cin >> n >> m; vector party[m+1]; queue q; memset(ch,false,sizeof(ch)); // 배열 초기화 memse..

문제 링크 : www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 간만에 추억의 게임이 언급되어 마음을 훈훈하게 만드는 문제였다. 문제 풀이는 다음과 같다. 1. 먼저 필요한 변수들을 선언한다. 전역변수이건 지역변수이건 상관없다. int n,m,x,y,u,v,pos,num,npos,nnum,ans,up[101],down[101],cnt[101]; bool ch[101]; 일부로 문제에서 요구하는 사항들을 그대로 맞추..

문제 링크 : www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 이 문제는 지문을 너무 대충 읽고 넘어갔다가 몇 번 틀리고 말았다. 먼저 지문을 자세히 읽고 유의 사항을 짚어보자. 1. 이 문제에서 시작 정점은 1이다. -> 입력 순서는 무조건 1부터 시작하지 않을 수 있다. 때문에 입력 순서의 첫 번째가 1이 아닐 경우 무조건 틀린 순서이다. 2. X와 연결되어있으면, 아직 방문하지 않은 정점 Y를 모두 큐에 넣는다 + 트리가 주어졌을 때 -> 이 해설 때문에 아래와 같은 트리 구조의 가능한 순서와 불가능한 순서는 다음과 같다. 1 -> 2 -> 3 -> 4 -> 5 -> ..

문제 링크 : www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 이 문제의 관건은 다음과 같다. 위 이미지에 표시된 치즈 내부에 있는 구멍과 외부 공기를 구분하는 것이다. 문제 풀이는 다음과 같다. 1. 먼저 아래코드는 공기와 접촉된 모든 치즈들을 녹이는 코드이다. 대략적으로 훑어보고 다음 차례에서 세세한 설명을 이해해보자. while(true){ done = false; cheese = 0; outofcheese(1,1); // 치즈 밖의 공기들만 별도로 표시해주는 ..

문제 링크 : www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 이 문제는 유의 사항이 하나 있다. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다. 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다. 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다. 예를 들어 하루 동안 위와 같은 인구이동 구역이..

문제 링크 : www.acmicpc.net/problem/21462146번: 다리 만들기여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다www.acmicpc.netBFS를 활용해서 풀 수 있는 문제다. 문제를 풀기 전에, 먼저 고민해야할 영역은 다음과 같다.1. 섬과 섬을 구분하는 방법-> 여러가지 방법이 있겠지만, 나는 각 섬마다 모두 똑같은 1이 아닌 고유의 값을 가지게 해서 구분했다.예를들어 어떤 섬은 2의 값만 가지게 하고, 어떤 섬은 3의 값만 가지게 하는 방식이다. 2. 섬과 섬의 최단 거리를 계산하는 방법-> 문제를 유심히 지켜보니 섬과 섬의 최단 거리 공..

문제 링크 : www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 사이클이 나오는 지점을 찾으면 되는 문제이다. 문제풀이는 다음과 같다. 1. 양방향 간선을 모두 입력 받는다. 2. int형 인자를 2개 넘겨받는 int형 함수 go를 만든다. 코드는 다음과 같다. int go(int x, int p){ // 현재 노드, 직전 방문 노드 if(check[x]==1) return x; // 방문한 적이 있는 노드라면 해당 노드를 반환 ch..

문제 링크 : www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 로직을 먼저 정하지 않고 대충보면서 풀다가 놓친 부분이 몇몇 있었던 문제이다. 먼저 이 문제에서 유의사항은 다음과 같다. 1. 숫자가 아닌 문자열로 주어진다. 2. 세로, 가로가 아닌 가로, 세로로 n과 m이 주어진다. 문제 풀이는 다음과 같다. 1. 가로, 세로로 값이 주어진다. 때문에 편의를 위해 n,m이 아닌 m,n의 순서로 값을 입력 받는다. 2. 숫자가 아닌 문자로 ..

문제 링크 : www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 전형적인 BFS문제이다. 여기에 누적 시간을 기록하기 위해 약간의 DP 개념을 활용하면 된다. 문제에서 사용자가 움직일 수 있는 범위는 크게 3가지로 분류된다. (화면 = sc, 클립보드 = cl) 1. 화면에 있는 이모티콘을 클립보드에 저장 (이때 기존 클립보드에 있는 내용은 모두 날라가고 덮어쓰기 됨) (sc, cl) -> (sc, sc) 2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 (..