https://www.acmicpc.net/problem/18808 #include #include using namespace std; int n, m, k; int turn; int st_l, st_w; struct sticker { int x_len, y_len; }; void rotateSticker(vector& stic) { int width = stic[0].size(); int length = stic.size(); vector tmp(width, vector(length)); for (int i = 0; i < length; i++) { for (int j = 0; j < width; j++) { tmp[j][length-1-i] = stic[i][j]; } } stic = tmp; } ..

문제 : 백준 17836번 _ 공주님을 구해라! https://www.acmicpc.net/problem/17836 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 2465 566 431 21.923% 문제 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다. 마왕은 용사를 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출하고 프러포즈 하고 ..

문제 : 백준 1260번 _ DFS와 BFS 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 87845 28912 16832 31.543% 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로..

문제 가장 멤버가 많은 아이돌 그룹으로 기네스 북에 올라 있는 혼성 팝 그룹 하이퍼시니어가 데뷔 10주년 기념 팬 미팅을 개최했습니다. 팬 미팅의 한 순서로, 멤버들과 참가한 팬들이 포옹을 하는 행사를 갖기로 했습니다. 하이퍼시니어의 멤버들은 우선 무대에 일렬로 섭니다. 팬 미팅에 참가한 M명의 팬들은 줄을 서서 맨 오른쪽 멤버에서부터 시작해 한 명씩 왼쪽으로 움직이며 멤버들과 하나씩 포옹을 합니다. 모든 팬들은 동시에 한 명씩 움직입니다. 아래 그림은 행사 과정의 일부를 보여줍니다. a~d는 네 명의 하이퍼시니어 멤버들이고, 0~5는 여섯 명의 팬들입니다. 하지만 하이퍼시니어의 남성 멤버들이 남성 팬과 포옹하기가 민망하다고 여겨서, 남성 팬과는 포옹 대신 악수를 하기로 했습니다. 줄을 선 멤버들과 팬들..

세그먼트 트리 https://www.acmicpc.net/blog/view/9 백준님 글 배열 크기 결정 세그먼트 트리를 만들기 위해서 C++의 경우, vector 자료형을 사용하는데 python으로 구현할 것이기 때문에 배열을 사용하려고 한다. 배열의 크기가 얼마나 되어야 할지 가늠하기 위해 크기를 결정해보자. 2의 제곱 수가 리프 노드의 수(n)로 주어진다면 ( 분석해야할 data 갯수가 2의 제곱 수라면 ) 각 단계마다 1/2씩 줄어나가므로 log(n)이 필요한 총 단계(화살표)가 되고 전체 층의 갯수, 즉 높이(h)는 log(n)+1이 된다. 최상위 노드부터 2^(0)개의 노드로 시작하여 층이 증가할 수록 2의 지수 또한 증가하기 때문에 꽉찬 이중 트리(full binary tree)의 총 노드 ..

공주님을 구해라! 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 2397 551 418 22.012% 문제 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다. 마왕은 용사가 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출하고 프러포즈를 반드시 하고 싶은 용사는 T시간 내에 반드시 공주님이 있는 곳으로 도달해야 한다. 용사는 한 칸을 이동..

달팽이 리스트 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 597 219 175 40.984% 문제 영진이는 달팽이를 좋아한다. 달팽이를 너무너무 좋아하기 때문에 특정한 모양의 단방향 연결리스트에 달팽이 리스트라는 이름을 붙여주었다. 일반적인 선형 단방향 연결리스트의 각 노드 번호를 연결된 순서대로 1, 2, ..., N이라 하자. 이때 N번 노드는 아무 노드도 가리키지 않는데, 여기서 N번 노드가 1번 노드를 제외한 임의의 노드를 가리켜 사이클을 이루게 되는 리스트를 달팽이 리스트라고 한다. 달팽이 리스트는 각 노드당 하나의 정수를 저장한다. 즉, 달팽이 리스트는 다음과 같이 생긴 연결리스트이다. 노드 안의 수는 저장된 값을 뜻한다. "달팽아 달팽아 1번 노드부터 한 칸씩..

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 20321 8384 6181 41.113% 문제 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다. 주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에..