반례
17472_다리만들기2(Python,설명) 반례...?
https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 삼성A형 기출문제라서 살짝 긴장하고 풀었다. 어려운 문제였다... 시간도 많이 걸렸지만 스스로 풀어서 되게 뿌듯한 문제였다. 아래와 같은 과정으로 순서대로 해결하여 접근하였다. 1. 문제에서 입력으로 준 지도를 2차원 리스트에 저장 2. 각 좌표를 트리구조처럼 만들기 위해 부모 배열을 만든다. 이때 부모배열또한 2차원으로 자신을 가르키도록 만든다. 3. 해당 구조에 맞는 fi..
4195_친구네트워크 ...반례?
https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 유니온 알고리즘을 활용하면 풀 수 있다. 우선 입력케이스로는 문자열이 나왔는데 이를 해결하기 위해서 딕셔너리를 사용해야 편하다. 즉, 사람 이름이 들어온다면 이를 인덱스로 삼는 형태로 해야 문제를 편하게 쓸 수 있다. 또한 친구네트워크의 개수가 필요한데, 나는 문제를 풀때 parents 딕셔너리안에 { ['이름' , 크기] } 식으로 저장했는데 문제를 풀고 생각해보니 그냥 조상을 저장하..
6549_히스토그램에서 가장 큰 직사각형(반례 모음)
문제는 더보기! 더보기 히스토그램에서 가장 큰 직사각형 성공다국어 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 34137 8911 5736 25.762% 문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. 입력 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의..
4949_균형잡힌 세상 ...반례?
문제는 더보기! 더보기 균형잡힌 세상 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 128 MB 49843 16453 13029 32.496% 문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 ..
2580_스도쿠...반례??
문제는 더보기! 더보기 더보기 문제 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다. 또한 위쪽 가..