평범한 회사 일기

www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 여행을 가고 싶어서 풀기 시작해서 화난 문제이다. 와 진짜 상상도 못한 곳에서 어이가 없어진 문제였다. 아이디어는 다음과 같다. BFS나 DFS를 사용할 수 있다면 편하게 풀 수 있는 문제. Destination을 따로 받는다. 그렇게 된다면 1 2 4 5 이런 식으로 될텐데 destination[1]부터 bfs를 돌려서 destination[i-1]에서 시작해 destination[i]에 도착하면 그냥 tru..

www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 사나이는 무릎꿇지 않는다. 잠들지 않는다. 임전무퇴 생즉사 쉐끼야. 뭐... 게임 트리를 C++로 구현하는 기분이라 오묘했다. 그 뭐였더라.. 어 디버깅은 어느정도 범위 넘어가면 프린트 해서 보자 라는 다짐을 또 가슴속에 새겼다. 근데 또 까먹겠지? 또 좀 막히면 에어에엉ㅇ 거리다가 F10이나 쳐 누르고 앉아있겠지? 그러지 말자 제발. #include #include using namespace std; int N; vecto..

오우... 이건... 응... 9 뚫기가 좀 어려웠고 나머지는 괜찮았다. 하나 뚫으면 나머지가 쭉쭉 풀리는 느낌이라고 해야하나? 여기서... 예시로 들만한게 있을거다. 9번을 하자. www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #include #include #include using namespace std; int n, m, len = 0; vector ans; vector ha; bool check[10001] = { false }; vector..

www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 알고보니 1+2였다. #include #include #include #include using namespace std; int main(){ cin.tie(0); cout.tie(0); int N; cin >> N; priority_queue ansP; priority_queue ansN; while (N--) { int tmp; cin >> tmp; if (tmp == 0) { if ..

www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 하나를 풀면 다른 하나도 풀 수 있는 1+1 떨이 행사 같은 문제이다. 왜냐..

www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 재밌었다. 어차피 각 가방에 하나씩밖에 안 들어간다는 뜻이니까, 들어갈 수 있는 보석의 가격을 최대힙(STL-priority_queue)으로 저장한 다음, 더 이상 안 들어가면 최대 가격을 ans에다 저장해주면 되는 문제였다. #include #include #include #include using namespace std; int main() { ..

www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 또또또또또또또또또 그놈의 scanf printf 아니면 시간초과라니 진절머리가 난다. #pragma warning(disable: 4996) #include #include using namespace std; int check(vector paper, int size) { int standard= paper[0][0]; for (int i = 0; i < size; ++i) { for (int j ..

www.acmicpc.net/problem/16916 와 이렇게 못된 문제는 처음이다. 내가 짠 코드가 시간초과가 계속 나길래 다른 사람 코드를 봤다. 그런데, 차이가 없는거다! 세상에! 그래서 하나하나 따져보기 시작했다. string의 size를 구하는 과정에서 났을까... 아니면 어디서 났을까... 하면서 매우 쫀쫀하게 짜보았다. cin.tie(0), cout.tie(0) 이런것도 썼다. 한번도 쓴 적이 없는데! 와! 뭐 어쨌든... 결론은 인덱스 0을 무시하면 시간초과가 나지 않았다는거다. 솔직히 좀 어이가 없긴 한데, 그렇다. ans[0]을 size 초기화해주면 시간 초과가 난다. 물론 그게 불필요한건 아는데(어차피 0일 테니까), 나를 화나게 한다. 만약 이 문제 풀거면 풀기 전에 화를 가라앉히..

www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 색종이 문제랑 똑같은데 왜 랭크는 높은지 1도 이해할 수 없는 문제다. 똑같이 풀었다. 아니 사실 다른 점이 있긴 한데, 그냥... 내가 자른 것이 내 생각대로 잘리진 않아서 코드 한 60번째 줄 보면 2랑 3이랑 바뀌어있을거다. 그거다. 확인해보고 싶으면 출력하면 된다. #include #include using namespace std; int check(vector paper, int size..

www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 이런 문제다. 그렇다면, 분할정복 기법을 사용한다. 어차피 1*1 2*2 4*4 .... 이런 것들만 있으니까 안되면 자르고 되면 넣고 하면 된다. 단순한 문제, #include #include using namespace std; int cutting(vector &ans, vector paper, int size); int check(vector paper, int size); i..