[Finite Automata, computational geometry] 내부점 판별 (in_out)
프로그램 명: in_out(open)
그림과 같이 사각형의 중심의 좌표가 주어지고 다른 한 점이 주어질 때 이 점이 사각형 내부의 점 인지 아닌지를 판별하는 문제이다.
입력
- 첫 줄에는 중심의 좌표와 중심에서 꼭지점 사이거리가
- 두 번째 줄에는 판별할 점의 좌표가 주어진다.
출력
내부의 점이면 yes , 아니면 no 를 출력한다.입출력 예
입력 2 2 3 -1 2 출력 yes 입력 2 2 3 -1 3 출력 no
math.h에 abs함수 즉, 절대값을 구하는 함수가 내장되어 있습니다.
하지만 dovelet에서는 gcc로 채점을 하기 때문에 채점되지 않기 때문에
abs함수를 직접 만들어서 사용하였습니다.
* 함수 설명
int abs( int x ) {
if ( x < 0 ) return x * -1; //만약 x가 0 보다 작다면(음수), x에 -1을 곱하여 리턴한다.return x; // 전 if 문에서 걸리지 않으면 그대로 리턴한다. }
즉, 음수에다가 -1을 곱해주면 양수(자연수)가 된다.
ex) -1 * -1 = 1, -356 * -1 = 356
if문 밑에 else를 쓰나 않 쓰나 같기 때문에 저는 쓰지 않았습니다.
어차피 if문에 걸리면 함수에서 나가니까요.
나는 [질/답] 에 힌트를 올려주신 graciful님께 감사를 표한다.
[질/답]에 보면 마름보 방정식을 이용하면 더 쉽다는 graciful님의
글이 올라와 있다.
'프로그래밍 > 알고리즘' 카테고리의 다른 글
| [BOJ] 1007번. Vector Matching (0) | 2017.11.22 |
|---|---|
| 프로그램 명: suffix_array(open) (0) | 2012.06.22 |
| [더블릿] KnapSack (0) | 2012.01.06 |
| [더블릿] 행오버 (0) | 2012.01.04 |
| 버스 (0) | 2012.01.03 |
[더블릿] KnapSack
각각의 보석의 무게(weight)와 값(value)을 가지고 있다. 무게 n 으로 어떤 보석을 가져 가는게 가장 많은 이윤(?)을 취할 수 있는 가를 구하는게 문제이다.
단, 보석은 쪼갤 수 없고 종류당 하나씩 있다고 하자.
입력 방법
입력의- 첫 줄에는 도둑이 가져갈 수 있는 무게를,
- 다음 줄에는 보석의 개수,
- 다음 줄 부터는 각 보석의 무게와 값이 한 줄에 하나씩 입력된다.
가방의 크기는 10000 이하이고 , 보석의 개수는 100 개 이하 무게와 가격은 200 이하의 정수이다.
출력 방법
첫 줄에 최대 이윤을 출력한다.입출력 예
입력 30 3 5 50 10 60 20 140 출력 200
#include <stdio.h> #define MAX 31 int arr[MAX][MAX]={0},w[MAX]={0},p[MAX]={0}; int i,j,n,m; int main() { scanf("%d %d",&m,&n); for(i = 1; i <= n; i++) scanf("%d %d",&w[i],&p[i]); for(i = 1; i <= n; i++) for(j = 1; j <= m; j++){ if(w[i] <= j && arr[i-1][j] <= arr[i-1][j-w[i]]+p[i]) arr[i][j] = arr[i-1][j-w[i]]+p[i]; else arr[i][j] = arr[i-1][j]; } printf("%d\n",arr[n][m]); return 0; }
여기서 값을 a만의 이윤을 구한 표의 똑같은 자리와 이윤을 비교하여 값을 넣으면 됩니다.
이렇게 풀면 됩니다.
구해 놓은 값을 참조하는 전형적 다이나믹 알고리즘 문제입니다.
'프로그래밍 > 알고리즘' 카테고리의 다른 글
| 프로그램 명: suffix_array(open) (0) | 2012.06.22 |
|---|---|
| [Finite Automata, computational geometry] 내부점 판별 (in_out) (0) | 2012.01.16 |
| [더블릿] 행오버 (0) | 2012.01.04 |
| 버스 (0) | 2012.01.03 |
| 촌수 계산[백트래킹] (0) | 2011.12.30 |
[더블릿] 행오버
얼마나 멀리 테이블 위에 카드를 쌓아 돌출 시킬 수 있을까?
만약 카드 한장을 가지고 있다면 카드 길이의 반 만큼의 돌출부를 만들 수 있다. (카드는 반드시 테이블에 수직으로 놓는다) 카드가 두개 있으면 맨 위의 카드는 아래 카드 위에 카드 길이의 반만큼 돌출 할 수 있고, 바닥의 카드는 테이블위에 카드 길이의 1/3만큼 돌출 할 수 있다. 따라서 돌출부분의 총 합은 카드 길이의 5/6(1/2+1/3)이 된다.
일반적으로 n개의 카드를 쌓아 돌출 시킬 때 가장 위에 있는 카드는 2번째 카드 위에 1/2이 돌출되어 있고, 2번째 카드는 3번째 카드에 1/3이, 3번째 카드는 4번째 카드위에 1/4이, .. 그리고 바닥의 카드는 테이블 위에 1/(n+1)이 돌출되어 총 길이는 카드길이의 1/2 + 1/3 + 1/4 + ... + 1/(n+1) 이 된다.
이 모습을 아래 그림에 나타내었다.
입력
입력의 첫 줄에 양의 실수 c 가 주어진다. 이 값은 적어도 0.01 이상 5.20 이하이다. 총 자리수는 세자리.출력
각각의 테스트 케이스에 대하여 적어도 입력 c 만큼의 카드 길이를 만들 수 있는 최소한의 필요 카드 개수를 출력하라. 예를 보고 정확한 출력 양식을 사용하라.입출력 예
입력 1.00 출력 3 card(s) 입력 3.71 출력 61 card(s) 입력 0.04 출력 1 card(s) 입력 5.19 출력 273 card(s)
출처: Mid-Central USA 2001 번역: makecode
#include <stdio.h>
int main() {
double c, n;
int cnt = 0;
scanf("%lf", &c);
for (n = 2; c > 0; n++, cnt++)
c -= 1/n;
printf("%d card(s)", cnt);
return 0;
}
'프로그래밍 > 알고리즘' 카테고리의 다른 글
| 프로그램 명: suffix_array(open) (0) | 2012.06.22 |
|---|---|
| [Finite Automata, computational geometry] 내부점 판별 (in_out) (0) | 2012.01.16 |
| [더블릿] KnapSack (0) | 2012.01.06 |
| 버스 (0) | 2012.01.03 |
| 촌수 계산[백트래킹] (0) | 2011.12.30 |
버스
어느날 공연을 마치고 버스를 타고 돌아가던 피에로는 창밖을 보다가, 바로 옆을 지나치는 버스를 보고 문득 한가지 궁금한 점이 생겼다.
'바로 옆의 지나가는 버스와 같은 번호의 버스는 몇분 뒤에 보게 될까?'
다행히 피에로는 최신 스마트폰을 가지고 있기 때문에, 현재 타고 있는 버스와 옆을 지나가는 버스의 배차간격을 알 수 있다.
배차간격이란, 모든 버스가 버스회사로부터 10km를 이동했을 때 다음 버스가 출발하는데, 첫번째 버스가 출발한 시간을 기준으로 두번째 버스가 출발할 때까지 걸린 시간을 의미한다.
하지만, 바로 옆을 지나치는 버스가 같은 방향의 버스인지 다른 방향인지에 따라 마주치게 되는 시간이 달라질 것이다.
지나친 버스의 방향과 두 버스의 배차간격이 주어질 때, 버스가 몇 분 뒤에 마주칠지 계산하기 귀찮아하는 피에로를 대신해서 계산해주자.
입력
입력의 끝이 EOF 일때까지 각 데이터마다 공백으로 구분되어 입력된다.각 데이터별
- 첫 줄에는 바로 옆을 지나치는 버스의 방향이 입력된다. 동일한 방향일때는 1을, 마주보는 방향일때는 0이 입력된다.
- 두번째 줄에는 피에로가 타고 있는 버스의 배차간격이 자연수로 주어진다.
- 세번째 줄에는 옆을 지나친 버스의 배차간격이 자연수로 주어진다.
출력
각 줄마다 같은 번호의 다른 버스를 마주칠 때까지 걸린 시간을 소수 둘째자리까지 출력해주자. 만약 마주치지 못한다면, "-1"을 출력해주자.입출력 예
입력 1 15 13 0 15 15 1 15 15 출력 97.50 7.50 -1
수정 소스
#include <stdio.h>
int main(){
int sw=0;
double A=0,B=0;
while(scanf("%d %lf %lf",&sw,&A,&B)!=EOF){
if(sw==1){
if( A < B) printf("%.2f\n",1/(1/A-1/B));
else if( A == B) printf("%d\n",-1);
else printf("%.2f\n",1/(1/B-1/A));
}
else{
if(A <= B) printf("%.2f\n",1/(1/A+1/B));
else printf("%.2f\n",1/(1/B+1/A));
}
}
return 0;
}
'프로그래밍 > 알고리즘' 카테고리의 다른 글
| 프로그램 명: suffix_array(open) (0) | 2012.06.22 |
|---|---|
| [Finite Automata, computational geometry] 내부점 판별 (in_out) (0) | 2012.01.16 |
| [더블릿] KnapSack (0) | 2012.01.06 |
| [더블릿] 행오버 (0) | 2012.01.04 |
| 촌수 계산[백트래킹] (0) | 2011.12.30 |
촌수 계산[백트래킹]
우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌이므로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌이므로 나와 아버지 형제들과는 3촌이 된다. 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.
실행 파일의 이름은 FAMILY.EXE로 하고, 프로그램의 실행시간은 10초를 초과할 수 없다. 정확한 답에 대하여서는 만점으로 채점하고, 틀린 답에 대하여서는 0점으로 채점한다.
입력 형식
입력 파일명은 INPUT.TXT로 한다. 사람들은 1,2,3,...,n(1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m 이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호x y가 각 줄에 나온다. 이때 앞에 나오는 번호 x 는 뒤에 나오는 정수 y 의 부모 번호를 나타낸다.
출력 형식
출력 파일명은 OUTPUT.TXT로 한다. 입력 파일에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람간의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이 때에는 -1을 출력해야한다.
입력과 출력의 예(1)
다음은 9명의 사람으로 구성된 촌수 관계에서 7번과 3번의 촌수를 구하는 입력 데이터의 예이다.
입력(INPUT.TXT)9
9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6
출력(OUTPUT.TXT)
3
입력과 출력의 예(2)
입력(INPUT.TXT)
9
8 6
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6
출력(OUTPUT.TXT)
-1
소스 :
#include <stdio.h>
#include <stdlib.h>
struct form {
int lnk[101];
}data[11];
void process(int k);
int n,m;
int cnt = 1, chk = 0;
int x,y, tmx, tmy, tmlx;
int main() {
int i;
scanf("%d", &n);
scanf("%d %d", &x, &y);
scanf("%d", &m);
for (i = 1; i<= m; i++) {
scanf(" %d %d", &tmx, &tmy);
data[tmx].lnk[tmy] = data[tmy].lnk[tmx] = 1;
if (tmy == x) tmlx = tmx;
}
process(tmlx);
if (chk == 0)
printf("%d", cnt);
else
printf("-1");
return 0;
}
void process(int k) {
int i;
if (k == y)
return;
for (i = 1; i <= n; i++) {
if ( data[i].lnk[k] == 1 ) {
cnt++;
data[k].lnk[i] = 0;
process(i);
return;
}
}
chk = 1;
}
솔직히 제 소스에 나와있는 구조체 필요 없습니다.
구조체 없이 차라리 2차원 써도되요.
제가 만든 구조체가 2차원 형태이기 때문이죠.
백트래킹으로 풀었으나, 인터넷에는 플로이드로도 할 수 있다네요.
'프로그래밍 > 알고리즘' 카테고리의 다른 글
| 프로그램 명: suffix_array(open) (0) | 2012.06.22 |
|---|---|
| [Finite Automata, computational geometry] 내부점 판별 (in_out) (0) | 2012.01.16 |
| [더블릿] KnapSack (0) | 2012.01.06 |
| [더블릿] 행오버 (0) | 2012.01.04 |
| 버스 (0) | 2012.01.03 |
