2011 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8907 에서 채점할 수 있습니다. 풀이 ) 1) '단색 삼각형의 수 = 모든 삼각형의 수 - 두 개의 색이 있는 삼각형의 수' 입니다. 2) '모든 삼각형의 수 = n*(n-1)*(n-2)/6' 입니다. () 3) '두 개의 색이 있는 삼각형' 은 아래의 두 가지 경우가 있습니다. 이 두 가지 경우의 공통점을 찾아보면 서로 다른 색의 간선이 연결된 꼭지점이 2개라는 점이 있습니다. 따라서 위와 같이(서로 다른 색의 두 간선이 한 꼭지점에 연결된 경우의 수) / 2를 구하면 '두 개의 색이 있는 삼각형'의 수를 구할 수 있습니다. cnt[i] = 꼭지점 i에 연결된 빨간색 선의 개수 위와 같은 cnt 배열을 구하면 으로 서로..
(0) [BOJ 10828] 스택 문제에 주어진 함수들을 그대로 구현하면 해결할 수 있습니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960//code by RiKang, weeklyps.com #include typedef int node_type;const int stack_size_max = 1000000; struct DS_stack{ int stack_size=0; node_type arr[stack_size_max]; node_type top(){ if(stack_size==0) return -1; return arr[stack_size-1]..
2011 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8901 에서 채점할 수 있습니다. 풀이 ) 1) 최초의 A의 양 = a, B의 양 = b, C의 양 = c, 그리고 최종적으로 완성한 AB의 양 = i, BC의 양 = j인 경우를 생각해보겠습니다. 그러면 남은 A는 a-i개, C는 c-j개가 있습니다. 이들을 통해 만들 수 있는 CA의 양은 min(a-i,c-j)가 됨은 당연합니다. 굳이 A와 C를 남겨두지 않고 모두 CA로 바꾸는게 이득이기 때문이지요. 따라서 이 경우 답은 ab*i + bc*j + ca*min(a-i,c-j) 가 됩니다. 이때, AB의 양(i)과 BC의 양(j)은 최대 1000개이기 때문에 i=0~1000, j=0~1000인 경우를 모두 고려해보아도 제..
2011 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8911 에서 채점할 수 있습니다. 풀이 ) 1) 거북이가 거쳐간 모든 좌표들을 알 수 있다면, 직사각형의 크기는 (max_x-min_x) * (max_y-min_y) 로 구할 수 있습니다. (max_x = 거북이가 거쳐간 x 좌표중 최대값, min_x = 거북이가 거쳐간 x 좌표중 최소값, max_y, min_y 도 같은 식입니다.) 2) 이 문제와 같이 90도로 회전하면서 전진하는 상황은 아래의 배열을 선언하여 시뮬레이션할 수 있습니다. 123// code by RiKang, weeklyps.comint dx[4]={0, -1, 0, 1}; // 위쪽, 왼쪽, 아럐쪽, 오른쪽으로 1칸 갈 때 x좌표의 변화입니다.int d..
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8898에서 채점할 수 있습니다. 풀이 ) i 경기 이후에 j 경기를 취재할 수 있는 경우, 즉, 인 경우를 ( i -> j )라고 표현하겠습니다. 그러면 이 문제를 '취재할 수 없는 가장 큰 경기의 부분집합의 크기 구하는 문제'에서, '최소한의 경기들을 삭제해서 서로 간선이 없도록 하는 문제'로 바꿀 수 있습니다. 전체 경기 수 - 삭제한 경기 수가 답이 되기 때문이지요. 이제 다음과 같은 이분 그래프를 구성해 보겠습니다. ( i->j ) 인 경우, ( i -> n+j ) 로 간선을 그린 것입니다. (1->2), (2->3), (1->3) 의 경우입니다. 이 그래프에서 만일 최소한의 정점 쌍(2와 n+2를 동시에 없애는 것..
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8899 에서 채점할 수 있습니다. 풀이 ) 1) 문제 지문을 보면 German research group가 아래와 같은 사실이 보장한다고 나옵니다. There exists a square annulus A of minimum width containing N given points such that its bigger square is a smallest axis-parallel square containing the N points. 이 말에 따르면, 큰 정사각형을 'N개의 점을 모두 포함하는 가장 작은 정사각형' 중에서만 골라도 정답을 찾을 수 있습니다. 'N개의 점을 모두 포함하는 가장 작은 정사각형'의 한 변의 길이..
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8890 에서 채점할 수 있습니다. 요약 ) 동적계획법으로 해결할 수 있는 문제로, DP 문제의 정의를 아래와 같이 하면 dp[t1][t2][t3]로 정답을 알 수 있습니다. dp[i][j][k] = s1 -> i, s2 -> j, s3 -> k 로 갈 때의 정답 (3개의 경로의 가중치 합의 최대값) 주의해야 할 것은 경로 상의 정점이 중복되면 안된다는 점입니다. 간단한 DP 문제 정의로도 해결 가능함에도, 이 중복 제거 조건 때문에 문제가 까다롭게 느껴질 수 있습니다. 이 풀이에서는 max(i,j,k) = 1 인 dp[i][j][k]들부터, max(i,j,k) = n 인 dp[i][j][k]들까지, max(i,j,k) 순서..
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8889 에서 채점할 수 있습니다. 요약 ) 1) x, y 좌표의 최대값은 10억이지만, 갯수는 200만개 이하이기 때문에 좌표 압축을 통해 각각의 좌표를 1 ~ 200만으로 바꿀 수 있습니다. 2) 최대 높이인 영역이 꼭지점을 하나 이상 포함하기 때문에, 모든 꼭지점의 높이 중 최대 높이만 구해도 전체 좌표 중 최대 높이가 됩니다. 3) 특정 y좌표 (y1) 에 대한 segment tree를 통해, y좌표가 y1인 꼭지점(x1,y1)의 높이를 구할 수 있습니다.segment tree 는 아래의 식이 성립하도록 설정해야 합니다.0 ~ x1위치의 총합 = 좌표 (x1,y1) 꼭지점의 높이이는 y = y1직선과 등고선의 교차점을..
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8893 에서 채점할 수 있습니다. 요약 ) LRLLRLL 형식으로 주어지는 다각형이 y축으로 monotone 인지를 확인하면 해결할 수 있습니다. (x축은 y축과 비슷한 방법으로 해결 가능합니다.) y축으로 monotone이 아니기 위해선 y축 방향으로 오목한 부분이 있어야 합니다. 그래야 y축에 평행한 직선이 다각형을 여러 번 자를 수 있습니다. 다시 말하면 아래와 같은 진행 방향이 나와야만 y축으로 monotone이 아닙니다. 반시계 방향으로 돌아가기 때문에, y축 monotone에 영향을 끼치는 오목한 부분은 위의 두 가지 경우만이 존재합니다. 다시 말하면 이 두 가지 경우가 모두 없다면 monotone 이고, 둘 중..
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8894에서 채점할 수 있습니다. 요약 ) 가능한 모든 패턴, 즉, 1,2,...,9 으로 만들 수 있는 모든 순열(중복 허용 X)을 재귀호출로 찾아도 O(9!) 안에 찾을 수 있습니다. 그리고 9! = 362880 입니다. 따라서 이 문제는 모든 패턴을 찾아보면서 입력으로 들어온 그래프와 비교해 보아도 제한 시간을 맞춰 줄 수 있습니다. 문제에서 주어진 예외 사항들을 잘 고려하면서, 재귀호출을 이용하여 모든 패턴을 찾는 프로그램을 구현하면 해결할 수 있습니다. 구현이 핵심인 문제이기 때문에, 코드를 중심으로 봐주시기 바랍니다. 재료 준비 ) 1234567891011121314151617181920212223242526272..
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8891에서 채점할 수 있습니다. 요약 ) 이 문제는 '점 숫자로 x, y 좌표 구하는 함수'와 'x, y 좌표로 점 숫자를 구하는 함수' 를 구현하면 해결할 수 있습니다. 이 두 함수를 구하기 위해선 점 숫자의 특징을 잘 관찰해야 합니다. 점 숫자의 가장 큰 특징으로는 같은 대각선일 경우, 점 숫자가 하나 늘어날 때 마다 x++, y-- 가 된다는 점이 있습니다. 이 점을 최대한 활용하기 위해 '대각선 시작 지점의 점 숫자'들을 저장한 배열을 만들면 '점 숫자로 x, y 좌표 구하는 함수'와 'x, y 좌표로 점 숫자를 구하는 함수' 를 구현할 수 있습니다. x=1 일 때(대각선 시작 지점) 점 숫자 구하기 ) 123456..
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8895에서 채점할 수 있습니다. 요약 ) 문제는 높이가 1,2,...,n 인 n개의 막대를 일렬로 세울 때, 왼쪽에서 보이는 막대가 l개, 오른쪽에서 보이는 막대가 r개가 되는 경우의 수를 구하는 것입니다. 이 문제는 '문제'를 '하위 문제'들로 나누어 해결하는 동적계획법으로 해결할 수 있습니다. DP 배열 구하기 ) 먼저 DP문제를 정의해야 합니다. 다행히 이 문제는 있는 그대로, 아래처럼 DP를 정의해도 해결할 수 있습니다. dp[n][l][r] = n개의 막대, 왼쪽에서 보이는 막대가 l개, 오른쪽에서 보이는 막대가 r개일 때의 답 이제 하위 문제를 찾아야 합니다. 높이가 n인 막대의 위치를 기준으로 하위 문제를 설정..
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8896에서 채점할 수 있습니다. 요약 ) N개의 로봇이 모두 모여 가위 바위 보를 하는 문제입니다. 각 로봇이 R, S, P 중 무엇을 낼지 정해져 있으므로, 가위 바위 보를 통해 로봇이 탈락하고 살아남는 과정을 그대로 구현하면 됩니다. 여기에서는 아래와 같은 배열 alive 를 관리하면서 구현하였습니다. alive[i] = i번째 로봇이 아직 살아있는가? 살아있으면 yes, 탈락했으면 no 초기화 ) 123456// code by RiKang, weeklyps.comscanf("%d",&n);for(int i=1; i>s[i]; alive[i] = true;}cs 먼저 초기화 부분에선 모든 로봇이 살아있도록 설정합니다. ..
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8892 에서 채점할 수 있습니다. 요약 ) 문제는 k개의 단어가 주어졌을 때, 그 중 2개의 단어를 붙여서 만든 문자열 중 팰린드롬이 있으면 그 중 아무거나 출력하고, 팰린드롬이 없으면 0을 출력하는 것입니다. 친절하게도 모든 단어 길이의 합이 10000이하임이 보장되므로, 만들 수 있는 모든 문자열을 만들어서 하나 하나 검사하여도 제한 시간내에 해결할 수 있습니다. 팰린드롬 체크 함수 ) 모든 문자열을 검사하려면, 먼저 문자열이 팰린드롬인지를 검사하는 함수를 만들어야 합니다. 팰린드롬의 정의에 따라 아래와 같이 구현할 수 있습니다. 1234567// code by RiKang, weeklyps.combool is_pal(..
(0) [BOJ 1110] 더하기 사이클 1234567891011121314151617181920212223//code by RiKang, weeklyps.com#include int next_m(int v){ int v1 = v%10; // 1의 자리 int v2 = v/10; // 10의 자리 return v1*10 + (v1+v2)%10;} int main() { int n, m, ans=0; scanf("%d",&n); m = n; while(1){ // break; 전까지 무한루프 ans++; m = next_m(m); if(n==m){ // m이 초기값인 n으로 돌아왔으므로, 이 지점의 ans가 루프의 길이가 됨. printf("%d",ans); break; } } return 0;}Color..
(0) [BOJ 4999] 아! 12345678910111213//code by RiKang, weeklyps.com#include #include int main() { char a[1005]; char b[1005]; scanf("%s",a); scanf("%s",b); if(strlen(a)>=strlen(b)) printf("go"); else printf("no"); return 0;}Colored by Color Scriptercs (1) [BOJ 5026] 박사 과정 123456789101112131415161718192021222324252627282930//code by RiKang, weeklyps.com#include #include int main() { int n; char a[1..
백준 온라인 저지 채점 방법 (0) [BOJ 11654] 아스키 코드 123456789//code by RiKang, weeklyps.com#include int main(void) { char c; scanf("%c",&c); printf("%d",c); return 0;}cs (1) [BOJ 11721] 열 개씩 끊어 출력하기 123456789101112131415//code by RiKang, weeklyps.com#include #include int main(void) { char c[105]; scanf("%s",c); int n = strlen(c); for(int i=0; i
백준 온라인 저지 채점 방법 (0) [BOJ 10039] 평균 점수 점수 합계를 저장할 변수로 sum 을 선언하자. 5개의 변수를 입력 받으면서, 40보다 작다면 40, 40 이상이라면 점수 그대로 sum 에 더해준다. sum/5 가 정답. 123456789101112131415//code by RiKang, weeklyps.com#include int main(void) { int sum=0; int a[5]; for(int i=0; i40) sum+=a[i]; else sum+=40; } printf("%d",sum/5); return 0;}cs 사실 이 문제는 배열이 필요 없다. 굳이 저장하지 않고 한 번 쓰고 버릴 수 있기 때문이다. 123456789101112131415//code by RiKa..
백준 온라인 저지 채점 방법 반복문 기본 문제 C언어에 정수형 변수로 int가 있듯이, 실수형 변수로는 float 와 double이 있다. 이 두 변수형은 int와 달리 소수 표현이 가능하다. 아래와 같이 선언할 수 있다. 출처: http://weeklyps.com/entry/C언어-5-변수-2-실수형-변수 [weekly ps] (0) [BOJ 8393] 합 (for) 123456789101112//code by RiKang, weeklyps.com#includeint main(void){ int n; int a=0; scanf("%d",&n); for(int i=1; i
백준 온라인 저지 채점 방법 (0) [BOJ 9498] 시험 성적 12345678910111213141516171819202122#include int main(void){ int a; scanf("%d",&a); if(a>=90 && a=80 && a=70 && a=60 && a=80){ printf("B"); } else if(a>=70){ printf("C"); } else if(a>=60){ printf("D"); } else{ printf("F"); } return 0;}cs (1) [BOJ 10817] 세 수 12345678910111213141516171819202122#include int main(void){ int a, b, c; scanf("%d %d %d",&a,&b,&c); if(..
백준 온라인 저지 채점 방법 (0) [BOJ 1000] A+B 12345678#include int main(void) { int a, b; scanf("%d %d",&a,&b); printf("%d",a+b); return 0;}cs (1) [BOJ 10869] 사칙연산 123456789101112#include int main(void) { int a, b; scanf("%d %d",&a,&b); printf("%d\n",a+b); printf("%d\n",a-b); printf("%d\n",a*b); printf("%d\n",a/b); printf("%d\n",a%b); return 0;}cs (2) [BOJ 10430] 나머지 1234567891011#include int main(void) { ..
백준 온라인 저지 채점 방법
백준 온라인 저지 링크 1. 회원가입 최상단 우측의 회원가입 버튼을 클릭하고 가입합니다. 2. 원하는 문제로 들어가기 상단의 '문제' 탭을 이용해 문제들을 찾아보고, 원하는 문제로 들어갑니다. 해당 문제를 해결할 수 있는 프로그램을 작성한 후, '제출' 탭을 클릭합니다. 3. 제출 해당 문제 페이지의 '제출' 탭에 들어간 후, '언어' 부분에서 원하는 컴파일러 버전을 선택하고 소스 코드를 복사 붙여넣기 하여 제출합니다. 제출할 경우, 나오는 채점 현황 페이지에서 '맞았습니다!' 를 받아야 정확한 코드를 작성한 것입니다.
(0) [BOJ 2557] Hello World 123456#include int main(void) { printf("Hello World!"); return 0;}cs (1) [BOJ 7287] 등록 1234567#include int main(void) { printf("320\n"); printf("RiKang"); return 0;}cs 자신의 문제 수와 아이디를 출력해야 한다. (2) [BOJ 10172] 개 12345678910#include int main(void) { printf("|\\_/|\n"); printf("|q p| /}\n"); printf("( 0 )\"\"\"\\\n"); printf("|\"^\"\` |\n"); printf("||_/=\\\\__|"); return ..
Table of Contents 개요 O(n^2) 풀이 더 알아보기 : O(n log n) 풀이 1 더 알아보기 : O(n log n) 풀이 2 1. 개요 최장 증가 부분 수열 (longest increasing subsequence) 문제는 유명한 동적 계획법 활용 예시입니다. LIS 문제는 말 그대로 수열이 주어졌을 때, 수가 점점 증가하는 가장 긴 부분 수열을 찾는 문제입니다. 정확한 문제는 아래의 링크를 통해 확인할 수 있습니다. [BOJ 11053] 가장 긴 증가하는 부분 수열 2. O(n^2) 풀이 dp [ i ] = A [ i ] 를 마지막 원소로 하는 증가 부분 수열의 최장 길이 간단하게 위와 같이 dp 문제를 정의하면 해결할 수 있습니다. 이 dp의 정의는 A[1] ~ A[i] 수열의 L..
Table of Contents 개요 풀이 구현 더 알아보기 : 공간 복잡도 최적화 1. 개요 냅색 문제 ( 배낭 문제 ) 는 프로그래밍계에서 유명한 문제로서 요약하면, 담을 수 있는 무게의 최댓값이 있는 배낭, 그리고 무게와 가치를 가진 짐들이 있을 때 배낭에 넣을 짐들의 가치가 최대가 되도록 배낭에 넣을 짐들을 고르는 문제입니다. 이 문제는 짐을 쪼갤 수 있는 경우와 쪼갤 수 없는 경우로 나뉩니다. 이 중 쪼갤 수 없는 경우는 0/1 배낭 문제 ( 0/1 knapsack problem ) 이라고 불리며 동적 계획법으로 해결이 가능합니다. 아래의 링크를 통해 0/1 배낭 문제의 예시를 보고 코딩한 후, 채점해 볼 수 있습니다. 아래의 풀이와 구현은 이 문제를 기준으로 설명하므로 반드시 읽어보시길 바랍니..
선행 : 모스 알고리즘 모스 알고리즘으로 해결 가능하다. [Li, Ri] 쿼리 구간에 대해 COUNT[x] = (A[j]==x) 인 j 의 갯수 위와 같은 정보를 저장하자. 그러면 모스 알고리즘이 돌아가면서 COUNT[x] 값이 갱신될 때, 정답도 같이 갱신해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465// code by RiKang, weeklyps.com#include#include#include#define PII pair#define PIII pair using namespace::std; const int N = ..
선행 : 모스 알고리즘 모스 알고리즘으로 해결 가능하다. [Li, Ri] 쿼리 구간에 대해 COUNT[x] = (A[j]==x) 인 j 의 갯수 COUNT2[x] = (COUNT[j]==x) 인 j 의 갯수 위와 같은 정보를 저장한다면, COUNT2[x] !=0 을 만족하는 최대의 x가 정답이 됨은 문제 설명 상 자명하다. 또한, [Li, Ri] 일 때의 정답과 [L(i+1), R(i+1)] 일 때의 정답의 차이는 |L(i+1)-L(i)| + |R(i+1)-R(i)| 이하이다.(* 추가or삭제되는 A[j] 의 개수보다 정답이 더 크게 변할 순 없기 때문이다. 정답이 증가할 때와 감소할 때 모두 생각해 보면 간단히 증명 가능) 이를 이용해 'COUNT2[x] !=0 을 만족하는 최대의 x' 를 지속적으로 ..
풀이는 http://weeklyps.com/entry/%ED%8A%B8%EB%A6%AC%EC%97%90%EC%84%9C%EC%9D%98-%EB%AA%A8%EC%8A%A4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%99%9C%EC%9A%A9-Mos-algorithm-on-tree 이 곳에 서술 되어 있으므로, 상세한 사항은 아래의 소스로 대신한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979..