lastknight00

문제 링크 : [백준]교수님은 기다리지 않는다(3830) 문제 설명 N개의 샘플이 있고, M번 두 샘플간의 무게 관계가 M번 주어지거나, 두 샘플간의 무게 관계를 조회하는 쿼리가 주어집니다. 조회 쿼리가 주어지면, 그동안 주어진 샘플간의 관계를 이용하여 무게 관계를 유추할 수 있는지, 있다면 차이가 얼마나 나는지 출력하세요. 입력 N(샘플의 갯수, 1 m; if(!n)break; for(b=1;b>a>>b>>c; if(a=='!'){ cin>>d; u(b,c,d); }else{ if(f(b)==f(c))cout

문제 링크 : [백준]피리 부는 사나이(16724) 문제 설명 N * M 행렬이 주어지고, 각 칸에는 위, 아래, 왼쪽, 오른쪽으로 이동 할 수 있는 방향이 주어집니다. 안전지대를 지정하려는데, 어떤 칸에서 시작하더라도 안전지대에 갈 수 있어야 합니다. 안전지대를 최소 몇개를 지정해야 하는지 구하세요. 입력 N(행렬의 세로 길이, 1 c; for(j=0;j

문제 링크 : [백준]전구 끄기(14927) 문제 설명 N * N 크기의 배열에 전구가 켜져있는지에 대한 정보가 주어집니다. 한 곳의 전구를 켜거나 끄게 되면 그 위치와 함께 그 위치의 위, 아래, 왼쪽, 오른쪽까지 함께 전구의 상태가 바뀝니다.(켜져있는 상태 -> 꺼짐, 꺼져있는 상태 -> 켜짐) 모든 전구를 끄기 위해서는 최소 몇번 스위치를 눌려야 하는지 구하세요. 입력 N(배열의 크기, 2

문제 링크 : [백준]불 끄기(14939) 문제 설명 10 * 10의 크기의 배열에 불이 켜져있는지에 대한 정보가 주어집니다. 한 곳의 불을 켜거나 끄게 되면 그 위치와 함께 그 위치의 위, 아래, 왼쪽, 오른쪽까지 함께 불의 상태가 바뀝니다.(켜져있는 상태 -> 꺼짐, 꺼져있는 상태 -> 켜짐) 모든 불을 끄기 위해서는 최소 몇번 스위치를 눌려야 하는지 구하세요. 입력 Sij(#은 꺼져있는 상태, O는 켜져있는 상태) #O######## OOO####### #O######## ####OO#### ###O##O### ####OO#### ########## ########O# #######OOO ########O# 출력 4 카테고리 #브루트포스 #그리디 시간 복잡도 상한 O(2N) 이상으로도 가능합니다. ..

문제 링크 : [백준]카드 게임(16566) 문제 설명 1~N 사이의 수 중, M개의 중복없는 숫자가 주어집니다. K개의 수(Vi)가 주어지는데, 위에서 주어진 수 중, Vi보다 큰 수 중 가장 작은 수를 출력하세요. 단, 한번 사용한 수는 다시 사용 할 수 없습니다. 입력 N(주어질 수들의 범위, 1

문제 링크 : [백준]본대 산책2(12850) 문제 설명 그래프가 주어져있고, 1번 노드에서 출발하여, N번 이동해서 1번 노드로 돌아오는 경우의 수를 구하세요. 입력 N(이동횟수, 1 1); D ret; for(int i=0;i

문제 링크 : [백준]Dance Dance Revolution(2342) 문제 설명 두 발이 처음에는 위치 0에서 시작합니다. 왼쪽 발과 오른쪽 발을 주어진 위치(1,2,3,4)로 옮겨야 하며, 두 발중 아무 발이나 옮길 수 있습니다. 단, 옮긴 후, 두 발이 같은 위치에 있으면 안됩니다. 발을 옮길 때마다 아래와 같이 비용이 발생합니다. 0 -> 다른 곳 : 2 1 3, 2 4 : 4 같은 곳을 다시 밟는 경우 : 1 그 외 : 3 밟을 곳이 주어진다면 모두 밟는 경우 중 최소 비용을 구하세요. 입력 Bi(밟을 판의 위치, 0인 경우 종료, 최대 100,000개를 초과하여 주어지지 않습니다.) 1 2 2 4 0 출력 8 카테고리 #DP 시간 복잡도 상한 O(NlongN) 해결 방법 발판이 주어지면, 두..

문제 링크 : [백준] 거짓말(1043) 문제 설명 N명의 사람이 M개의 파티에 참석하려고 합니다. 지민이는 각 파티에서 거짓말을 하고 싶은데, 진실을 아는 사람이 K명이 있습니다. K명의 사람이 참석한 파티와 그 파티에 참석한 사람이 참석하는 다른 파티에서는 거짓말을 할 수 없습니다. 지민이는 최대 몇개의 파티에서 거짓말을 할 수 있는지 구하세요. 입력 N(사람 수, 1