티스토리

S. Kevin 창고

검색하기

블로그 홈

S. Kevin 창고

kevin0725.tistory.com/m

S. Kevin 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

[BOJ] 1149번. RGB거리 문제 링크 : https://www.acmicpc.net/problem/1149 문제는 링크 참고. 풀이. dy[i][j] : i번째집이 j번째 색으로 칠했을 때 들 수 있는 가장 적은 비용dy[i][j] = dy[i][j] + MIN(dy[i][(j + 1) % 3], dy[i][(j + 2) % 3]); 여기서 R은 0, G는 1, B는 2로 했다. 입력 예제 설명. 입력예제 : 3 26 40 83 49 60 57 13 89 99 0번째 집이 색칠 하는 경우R : 26G : 40B : 83 1번째 집이 색칠 하는 경우R : 49 + MIN(0번째 집 G를 칠 했을 때 비용, 0번째 집 B를 칠 했을 때 비용)G : 60 + MIN(0번째 집 R를 칠 했을 때 비용, 0번째 집 B를 칠 했을 때 비용).. 공감수 0 댓글수 0 2017. 12. 19.
[BOJ] 1032번. 명령 프롬프트 문제 링크 : https://www.acmicpc.net/problem/1032 문제는 링크 참고. 풀이.풀이가 필요한가? ㅋㅋ 문자열의 최대 길이가 50이기 때문에 그냥 생각 안하고, 머리에서 생각나는 대로 풀었다. 입력된 문자열 중, 문자열이 같은 부분만 찾아서 출력하고 나머지 부분은 '?'로 출력하면 된다. 123456789101112131415161718192021222324252627#include #include int main() { int N = 0, len = 0; char sFirst[51] = "", sTmp[51] = ""; bool bFlags[50] = {0}; scanf("%d", &N); scanf("%s", sFirst); len = strlen(sFirst); for (i.. 공감수 0 댓글수 0 2017. 12. 19.
[BOJ] 1015번. 수열 정렬 문제 링크 : https://www.acmicpc.net/problem/1015 문제는 링크 참고. 풀이. 문제에 나와 있듯이 "B[P[i]] = A[i]" 식을 이용해서 풀면된다. 입력예제 "2 3 1" 에서 출력예제 "1 2 0" 이 나오는 이유는 A { 2 3 1 }P { 1 2 0 } 이 있다면 B[P[0]] = A[0] = B[1] = 2B[P[1]] = A[1] = B[2] = 3B[P[2]] = A[2] = B[0] = 1 결과적으로 B { 2 3 1 }이 완성되고, B는 A로부터 정렬된 수열이란 것을 알 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #define .. 공감수 0 댓글수 0 2017. 12. 18.
[BOJ] 1013번. Contact 문제 링크 : https://www.acmicpc.net/problem/1013 문제는 링크 참고. 풀이. 이 문제는 각 문자마다 다음에 뭐가 올 수 있는지를 분석하여서도 풀 수 있다. 하지만 다음과 같이 그래프를 그려 각 문자를 검사하는 상황마다 인덱스를 매겨서 쉽게 풀 수도 있다. (100+1+ | 01)+ 패턴에 맞는 문자열을 위 그래프를 따라가면서 검사해보면 이 그래프가 왜 그려졌는지 쉽게 알 수 있다. 여기서 빨간색 원은 마지막으로 문자열을 검색했을 때 상태가 0번,4번,5번일 경우 맞는 문자열의 상태의 번호를 표시한다. ex1)문자열 : 10011001 은 상태가 0→1→2→3→4→5→6→3→4 로 끝나므로, 맞는 문자열이다. ex2)문자열 : 101101 은 상태가 0→1→2→8(정의되지 않.. 공감수 0 댓글수 0 2017. 12. 7.
[BOJ] 1012번. 유기농 배추 문제 링크 : https://www.acmicpc.net/problem/1012 문제는 링크 참고. 풀이. 이 문제는 딱 보고 생각나는 데로 풀면된다. 배추가 있는 부분을 찾아 그 부분의 갯수를 세어 출력하면 배추 흰 애벌레가 얼마나 필요한지 알 수 있다. 입력된 좌표를 돌면서 1을 찾았을 때, 그 부분의 1을 DFS를 이용하여 다 없애버리고 cnt ++을 하면된다. 여기서 시간을 좀 더 빠르게 하고 싶다면 입력된 좌표 갯수 만큼만 탐색을 하여 부분을 찾으면 조금 더 시간이 빨라질 수 있다.(우리가 인지할 만큼 빨라지지 않음) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545.. 공감수 0 댓글수 0 2017. 12. 4.
[BOJ] 1010번. 다리 놓기 문제 링크 : https://www.acmicpc.net/problem/1010 문제는 링크 참고. 풀이.N = 서쪽의 사이트 갯수, M = 동쪽의 사이트 갯수 N = 2, M = 4일 때를 가정해보자 N(1)번 사이트와 M(1)번 사이트를 연결하면 남는 사이트들은 서쪽 사이트 1개 동쪽 사이트 3개가 남는다.즉, N(1)번과 M(1)번을 연결하면 N = 1, M = 3 일 때의 가짓수가 나온다는 것이다. 그렇다면 마찬가지로 N(1)번과 M(2)번 사이트를 연결하면 남는 사이트들은 서쪽 사이트 1개 동쪽 사이트 2개가 남는다.이것 또한 N(1)번과 M(2)번 사이트를 연결하면 N = 1, M = 2개의 가짓수가 나온다는 것이다. 이렇게 각 사이트마다 연결하여 가짓수를 구하면 (N = 1, M = 3 가짓.. 공감수 0 댓글수 0 2017. 11. 27.
[BOJ] 1463번. 1로 만들기 사지방 시간이 없어서 급하게 올림. 문제 링크 : https://www.acmicpc.net/problem/1463 풀이: 숫자 10을 1로 만들 때, 10 9 3 1 이렇게 만들어진다.D[i] : 숫자 i를 1로 만들 수 있는 최소 연산 횟수. D[i] = MIN(D[i / 2], D[i / 3], D[i - 1]) + 1 단, D[i / 2], D[i / 3]은 i가 2로 나누어지거나, i가 3으로 나누어질 때만 참조 가능. **** 주의. 나눌 수 있다고 해서 나눈 값으로 참조하면 최소값이 되지 않는다.ex) 10 -> 9 -> 3 -> 1 과 10 -> 5 -> 4 -> 3 -> 1 중, 전자가 답이다. 1234567891011121314151617181920212223242526272829303.. 공감수 0 댓글수 0 2017. 11. 26.
[BOJ] 1008번. 분산처리 문제 링크 : https://www.acmicpc.net/problem/1009 문제명분산처리설 명문제재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다. 1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... , 10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ... 총 데이터의 개수는 항상 ab개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.입력입력의 첫 줄에는 테스트 케이스의.. 공감수 0 댓글수 0 2017. 11. 24.
[BOJ] 1007번. Vector Matching 문제 링크 : https://www.acmicpc.net/problem/1007 문제명Vector Matching설 명문제평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 Vector Matching은 벡터의 집합인데, 모든 벡터는 집합 P 중 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터들의 집합이다. 또, P속의 모든 점은 모두 단 한번만 쓰여야 한다. V에 있는 벡터의 개수는 P에 있는 점의 절반이다. 평면 상의 점이 주어졌을 때, 집합 P의 Vector Matching에 있는 벡터들의 합의 길이의 최소값을 출력하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다. 첫째 줄에 점의 개수 N이 주어진다. .. 공감수 0 댓글수 0 2017. 11. 22.
프로그램 명: suffix_array(open) 프로그램 명: suffix_array(open)제한시간: 1 초문자열 dovelet 이 주어질 때0123456dovelet이 문자열로 만들 수 있는 접미사는 7 개 이다.dovelet(0)ovelet(1)velet(2)elet(3)let(4)et(5)t(6)이 접미사 배열(suffix array)을 정렬하면dovelet(0)elet(3)et(5)let(4)ovelet(1)t(6)velet(2)입력입력은 2000 이하의 문자열이 주어진다.출력정렬한 접미사 배열을 출력한다. 문자열과 수 사이에는 한 칸의 공백을 둔다.입출력 예입력 dovelet 출력 dovelet 0 elet 3 et 5 let 4 ovelet 1 t 6 velet 2 #include #include #include #define M 201.. 공감수 2 댓글수 0 2012. 6. 22.
[Finite Automata, computational geometry] 내부점 판별 (in_out) 출처 : www.dovelet.com 공감수 2 댓글수 0 2012. 1. 16.
[더블릿] KnapSack 프로그램 명: 01knapsack 제한시간: 1 초 도둑이 보석상에 침입하여 보석을 훔쳐가려고 한다. 그런데 보석이 가져 갈수 있는 보석의 무게(n)은 한정되어 있다.각각의 보석의 무게(weight)와 값(value)을 가지고 있다. 무게 n 으로 어떤 보석을 가져 가는게 가장 많은 이윤(?)을 취할 수 있는 가를 구하는게 문제이다. 단, 보석은 쪼갤 수 없고 종류당 하나씩 있다고 하자. 입력 방법입력의 첫 줄에는 도둑이 가져갈 수 있는 무게를, 다음 줄에는 보석의 개수, 다음 줄 부터는 각 보석의 무게와 값이 한 줄에 하나씩 입력된다. 가방의 크기는 10000 이하이고 , 보석의 개수는 100 개 이하 무게와 가격은 200 이하의 정수이다. 출력 방법첫 줄에 최대 이윤을 출력한다.입출력 예입력 30 3.. 공감수 0 댓글수 0 2012. 1. 6.
[더블릿] 행오버 프로그램 명: hangover 제한시간: 1 초 얼마나 멀리 테이블 위에 카드를 쌓아 돌출 시킬 수 있을까? 만약 카드 한장을 가지고 있다면 카드 길이의 반 만큼의 돌출부를 만들 수 있다. (카드는 반드시 테이블에 수직으로 놓는다) 카드가 두개 있으면 맨 위의 카드는 아래 카드 위에 카드 길이의 반만큼 돌출 할 수 있고, 바닥의 카드는 테이블위에 카드 길이의 1/3만큼 돌출 할 수 있다. 따라서 돌출부분의 총 합은 카드 길이의 5/6(1/2+1/3)이 된다. 일반적으로 n개의 카드를 쌓아 돌출 시킬 때 가장 위에 있는 카드는 2번째 카드 위에 1/2이 돌출되어 있고, 2번째 카드는 3번째 카드에 1/3이, 3번째 카드는 4번째 카드위에 1/4이, .. 그리고 바닥의 카드는 테이블 위에 1/(n+1)이 돌.. 공감수 1 댓글수 0 2012. 1. 4.
버스 프로그램 명: bus 제한시간: 1 초 어느날 공연을 마치고 버스를 타고 돌아가던 피에로는 창밖을 보다가, 바로 옆을 지나치는 버스를 보고 문득 한가지 궁금한 점이 생겼다. '바로 옆의 지나가는 버스와 같은 번호의 버스는 몇분 뒤에 보게 될까?' 다행히 피에로는 최신 스마트폰을 가지고 있기 때문에, 현재 타고 있는 버스와 옆을 지나가는 버스의 배차간격을 알 수 있다. 배차간격이란, 모든 버스가 버스회사로부터 10km를 이동했을 때 다음 버스가 출발하는데, 첫번째 버스가 출발한 시간을 기준으로 두번째 버스가 출발할 때까지 걸린 시간을 의미한다. 하지만, 바로 옆을 지나치는 버스가 같은 방향의 버스인지 다른 방향인지에 따라 마주치게 되는 시간이 달라질 것이다. 지나친 버스의 방향과 두 버스의 배차간격이 주어.. 공감수 2 댓글수 0 2012. 1. 3.
촌수 계산[백트래킹] 한번만 눌러주세요! 촌수계산 우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌이므로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌이므로 나와 아버지 형제들과는 3촌이 된다. 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오. 실행 파일의 이름은 FAMILY.EXE로 하고, 프로그램의 실행시간은 10초를 초과할 수 없다. 정확한 답에 대하여서는 만점으로 채점하고, 틀린 답에 대하여서는 0점으로.. 공감수 1 댓글수 0 2011. 12. 30.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.