[7571] 점모으기
출처 : https://www.acmicpc.net/problem/7571 행의 크기와 열의 크기가 각각 N인 격자공간에 M개의 점이 있다. N = 4이고 M = 4인 경우의 예가 아래에 있다. 격자공간 왼쪽의 숫자는 행 번호이며, 위의 숫자는 열 번호를 나타낸다. 그리고 격자공간내의 각 사각형의 위치는 (행 번호, 열 번호)로 표시한다 이제 격자공간에 있는 모든 점들을 하나의 사각형 안으로 모으려고 한다. 어떤 점을 움직일 때는 그 점이 들어있는 사각형에서 상하좌우로 인접한 사각형으로만 움직일 수 있다. 여기에서는 격자공간내의 한 사각형으로 모든 점들을 모을 때 각 점이 움직인 거리의 합을 고려한다. 예를 들어, 위의 점들을 (3,2)에 있는 사각형으로 모을 때 최단거리로 점들을 이동시킨다면 (1,2)..
[2565] 전깃줄
문제 출처 : https://www.acmicpc.net/problem/2565 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 ..
[2418] 단어 격자아래와 같은 단어격자가 주어진다.이 격자내에서 읽을 수 있는 단어가 주어지면 주어진 단어를 읽을 수 있는 경우의 수를 출력하는 문제이다.(중복해서 칸을 이동하며 읽을 수 있고, 칸은 대각선, 아래, 위, 좌, 우 를 포함 8방향을 이동할 수 있다) 1) 메모이제이션 + 완전탐색각 단어격자의 문자를 시작 문자로 하여 주어진 단어를 만들 수 있는지 모두 체크한다. 123456789101112131415161718192021222324252627282930313233343536373839#include using namespace std; char puzzle[201][201], word[101];long long ans = 0; int l;long long d[201][201][101]..
[2529] 부등호부등호 n개의 배열이 주어지면,해당 부등호 들을 만족시키는 숫자 n+1개의 배열 중 가장 작은 숫자 배열과 가장 큰 숫자배열을 찾는 문제.부등호 배열 A = {} 가 주어지면 이를 만족하는 숫자는 0 1 , 1 2 , 2 3, ... , 8 7 과 같다.이 중 가장 큰 숫자 배열은 897이고, 가장 작은 숫자배열은 021이다. 1) 그냥 다 보기부등호가 기껏해봐야 9개가 주어지고, 10개의 숫자로 이루어진 배열이므로 최대 10!의 경우를 모두 보면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142#include #include using namespace std;..
문제 출처 : https://www.acmicpc.net/problem/5397분류 : 시뮬레이션, 스택, 링크드리스트 백준 5397 키로거시뮬레이션, 스택을 이용구현 포인트1) 직접 구현 시 중간 삽입을 어떻게 할 것인가? 스택 또는 링크드리스트! 처음에 아무생각 없이 코딩했을 때는 중간 삽입에 대한 생각 없이 풀었다.. 결과는 물론 시간초과 1초이내에 해낼리가 없다;; 그래서 링크드 리스트와 같은 time complexity를 보이는 deque를 사용하였다. 다른 사람들 코드리뷰를 해보니 스택을 이용하는 다른 방법도 있어서 글을 남기기로 하였다. 우선 내가 푼 코드는 아래와 같다. 1234567891011121314151617181920212223242526272829303132333435363738..
문제 출처 : https://www.acmicpc.net/problem/1072분류 : 수학, 이분탐색 백준 1072 게임parametric search구현 포인트1) 처음부터 99퍼나 100퍼라면 절대 증가할 수 없다.2) 이분 탐색으로 시간을 줄이자. 문제는 아래와 같다.문제김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.이제 형택이는 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭..
문제 출처 : https://www.acmicpc.net/problem/2011분류 : 다이나믹 프로그래밍 백준 2011 암호코드DP구현 포인트1) DP로 2자리로 끝나는 경우, 1자리로 끝나는 경우를 저장해준다.2) 해석이 안되는 경우에는 0을 찍어야 한다. 이 문제는 다소 쉬우나 정답률이 낮다. 이유는 나처럼 멍청한 사람들이 해석이 안되는 경우에 대해 고려하지 않아서... 일 것이라는 생각이 든다. 한창 그것 때문에 틀렸습니다가 떠서 여기 글을 남겨 놓기로 하였다. 코드는 아래와 같다. 12345678910111213141516171819202122232425#include#include#define MOD 1000000using namespace std; int DP[5000][2];int main..
문제 출처 : https://www.acmicpc.net/problem/11000분류 : 정렬 및 그리디 백준 11000 강의실 배정NlogN 안에 강의실을 모두 배정하여 보자구현 포인트1) 정렬을 하여 문제를 단순화 한다.2) priority queue를 이용하여 빠르게 강의실을 배정하자. 생각보다 문제 풀면서 뻘짓을 많이 해서 남기기로 했다.어처구니 없게도 처음에 강의 정보를 정렬해 놓고 생각을 너무 복잡하게 하였다...(각 종료시간을 set으로 저장한 후 iterator를 통해 현재 강의 정보의 시작시간과 비교하여 가장 차이가 작은 강의실에 해당 강의를 배정하는 그런 방식으로.. 물론 이 생각은 논리적으로 맞다.지금 각 강의실의 종료시간이 4, 5, 6이고, 배정하려는 강의의 시작시간이 7이라면 당..