[PS] BOJ 11657 타임머신

BOJ-11657 타임머신 https://www.acmicpc.net/problem/11657 본 문제는 시간 C가 음수가 나올 수 있기 때문에, 벨만-포드 알고리즘을 사용해야 한다. 음의 페로가 존재한다면 -1 만 »

[PS] BOJ 1865웜홀

BOJ-1865 웜홀 https://www.acmicpc.net/problem/1865 본래 벨만-포드 알고리즘은 방향그래프에서만 적용가능한 알고리즘이다. 하지만 본 문제에서는 웜홀만 방향이 있다고 설명한다. 따라서 우리는 지점과 지점사이에 가중치가 »

[PS] BOJ 2252 줄세우기

BOJ-2252 줄 세우기 https://www.acmicpc.net/problem/2252 본 문제는 단순히 입력을 인접리스트인 그래프로 만든뒤에, 위상정렬한 결과를 출력하면 된다. solution #include<iostream> #include& »

[PS] BOJ 1707이분 그래프

BOJ-1707 이분그래프 아래의 사이트는 이분그래프를 판별하는 문제이다. https://www.acmicpc.net/problem/1707 본 문제는, DFS 탐색을통해 Vertex를 색칠해가면서 색칠이 완성되면 이분그래프임을 확인하는 문제이다. 이분그래프 알고리즘에 »

[PS] 1002~1005, 1007 ~ 1013

problem1002 https://www.acmicpc.net/problem/1002 제곱근 계산이 들어가면 정밀도 때문에 정답을 맞추지 못한다 #!/usr/bin/perl my $t=<>; while($t--){ my $s= »

[PS] BOJ 1006습격자 초라기

DFS + memorized 방법으로 풀면 쉽다. 원형으로 된 배열을 처음과 끝을 분리하여 선형구조로 풀고, 지그재그 형태로 순서를 명시하고 각 원소에 해당되는 최소값을 table에 저장하여 memorized로 풀면 된다. »

[PS] Daejeon 4846 Mines

본 문제는 지뢰를 터트리는데, 최소한 으로 터트려야하는 개수를 출력하면된다. 다음과 같이 지뢰가 있을때, (1) 을 터트리면 (4)도 터지게 되고 (3),(6)도 터지게 된다. 그리고 »

[PS] 2010 Daejeon 4845 Password

본 문제는 각 열(col) 의 중복되는 알파벳을 찾아서 가능한 패스워드 집합중 N번째 원소를 출력하는 문제이다. 입력을 받고, 중복을 제거하고, 정렬을 하면 느리므로, 해싱으로 입력을 받아 »

[PS] 2010 Daejeon 4843 Sales

본 문제는 자신 앞에 자신보다 같거나 작은수의 개수를 모두 출력하는 문제이다. 주먹구구식으로 풀면 O(n^2) 시간에 풀 수 있지만 사실 이 문제는 BIT 문제이다(Binary »

[PS] 2012 Daejeon 6117 Pole Arrangement

입력이 3개가 들어온다. N L R이 들어온다 N은 길이가 전부 다른 막대기의 수이고, L은 왼쪽에서 봤을때 막대기의 개수 R은 오른쪽에서 보았을때 막대기의 개수이다. 본 문제는 가장 »

[PS] 2012 Daejeon 6114 palindrome

본 문제는 N개의 string이 주어졌을떄 두개의 스트링을 조합해 회문을 찾는 문제이다. 간단하게 O(N^2)으로 풀 수 있는데, 가능성이 없는 조합은 제외하는것이 포인트이다. A와 B를 »

[PS] 2013 Daejeon 6505 Metal

본 문제는 메탈(쇠구슬)의 좌표가 주어진다. 우리는 수평터널을 만들수 있다. 수평터널을 지나면서 메탈을 수집하는데, 가장 효율적으로 수평터널을 팠을때 가장 수집길이가 긴 메탈의 길이를 출력하는 문제이다. »

[PS] 2012 Daejeon 6113 Dot Number

본 문제는 입력이 값 2개가 들어온다. 다음 그림을 먼저 보자 예를들어 1 5 와 같이 입력이 들어왔으면 1과 5가 좌표 몇 몇에 있는지 알아낸다. 1은 (1, »

[PS] 2013 Daejeon 6508 Permutation Graphs

Permutation Graphs 란 구글에 치면 본 문제와 같은 그림이 많이 나온다. 원소의 개수와 원소의 내용이 같은데, 순서만 다른 두 배열을 주고 같은 원소끼리 선을 긋고 겹치는 »

[PS] 2013 Daejeon 6506 Padovan Sequence

본 문제는 달팽이 마냥 삼각형이 만들어져있는데, 변의 크기를 출력하는 문제이다 점화식은 A[i]= A[i-1] + A[i-5] 이고 런타임에 계산하면 느리므로 입출력만 런타임에 하도록한다. int 로는 »

[PS] 2012 Daejeon 6121 Square Annulus

TL이 10초짜리라 그런지, 설명이 좀 길다. 잘 보면된다. 문제를 간단히 요약하면, 모든점을 포함하는 정사각형을 그린후 내부점을 외곽으로 삼는 작은 정사각형을 그린다. 그런데 작은 정사각형은 큰 정사각형 »

[PS] 2011 Daejeon 5850 Turtle

이 문제는 문자값에 따라 거북이가 이동한 좌표의 사각 넓이를 구하는 문제이다. L,R은 방향만 트는 것이고 F와 B가 앞으로 또는 뒤로 이동한 거리이다. F와 B를 할때 »

[PS] 2013 Daejeon 6511 Term Project

본 문제는 간단하게 왕따를 찾는문제이다. 먼저 자신을 선택한 사람이 없으면 왕따이다. 이를 그래프로 표시해보면 위와 같이 2와 5는 선택받지 못했으므로 왕따이다. 이에 따라, 왕따가 선택한놈도 왕따일 »

[PS] 2013 Daejeon 6500 Boxes

문제는 너무 쉽다. 박스를 테트리스마냥 밑으로 내리는데, 몇번을 옮겨야 하느냐? 하는 문제이다. 가장 멍청한 솔루션은 직접 박스를 움직이는것이다. 이것을 간단한 동적계획법으로 풀수 있는데, 위에서 아래로 순회하면서, »

[PS] 2014 Daejeon 6897 Exploration

본 문제는, 솔루션보다 문제의 뜻을 이해하기가 더 어렵다. 그래프의 정점이 사람이고 간선이 관계를 뜻한다. 간선의 수가 친구의 수라고 볼 수 있는데, 이 친구의 수가 K개 이상인 »

[PS] 2014 Daejeon 6896 Eureka Theorem

본문제는 부가적으로 설명할 것이없다. 어떠한 수가 3개의 삼각수들로 이루어지면 그것이 유레카 숫자이다. 3중반복으로 풀어야징 ㅋ 하는 사람은 없길 바라며... 기본적으로 이중반복을 돌고 나머지는, 이진탐색으로 해가 있는지 »

[PS] 2014 Daejeon 6902 Three Squares

본 문제는 여러개의 점들을 정사각형 3개로 모두 감싸는데 가장 작은 정사각형의 변의 길이를 출력하는 문제이다. 3개를 구하는것이라 어려울 수 있는데. 2개라고 생각하면 매우 간단하다. 먼저 위 »

[PS] 2014 Daejeon 6895 Deduction

Deduction 의 뜻은 추론 이라는 뜻이다. 초반 설명이 이해하기 어렵지만 간략하게 요약하면 다음과 같다. TYPE1 은 무조건 참이다. TYPE2 는 [a,b,c...] -> false , 즉 »

[PS] [SC]두 숫자 더하기

main(n) { gets(&n); putchar(n % 85 + 5); } 위는 일의자리 두 숫자를 더하는 소스이다. 원리는 아래와 같다. 만일 0 0을 입력하면 0이 나오고 4 4를 »

[PS] 2013 Daejeon 6510 Stickers

본 문제는 스티커의 합이 최대가 되도록 뽑아야하는데, 인접한 스티커 두개는 뽑을 수 없다. 위와 같이 스티커가 있을떄, 맨 왼쪽 줄에 50을 골랐으면 밑에 30과 오른쪽의 10은 »

[PS] [DP] knapsack

배낭문제라 불리는 knapsack 문제이다. 가방에 담을수 있는 무게가 정해져 있고, 가방에 물건들을 담을때 , 가치가 최대가 되는 방법을 고르는 문제이다. dynamic programming에서 optimal solution은 항상 문제를 소분화에서 »

[PS] [DP] weighted interval scheduling

WIS 라 불리는 가중치를 가진 구간 문제이다. n개의 구간이 있고 각 구간마다 가중치(weight)를 갖는다. 겹치지 않게 구간을 선택하는데 , 가중치의 합이 가장큰 구간들을 고르는 문제이다. »