본문 바로가기

백준61

[BOJ] 백준 1014번: 컨닝 https://www.acmicpc.net/problem/1014 1014번: 컨닝 문제 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼 www.acmicpc.net 교실 정보가 주어질 때, 위의 그림처럼 컨닝이 가능해 A,C,D,E 중 한 자리라도 사람이 앉아있으면 컨닝을 방지하기 위하여 해당 자리를 앉지못하게 합니다. 위의 규칙을 만족하면서 최대한 몇명의 사람이 앉을 수 있는지 구하는 문제입니다. 저는 동적계획법으로 해결하였습니다. (입력이 10X10이므로 꽤 다양한 알고리즘으로 해결가능하다고 생각합니다.) DP[i][j] 는 i-1번째 줄에 j 상태로 앉아있을 때 i번째.. 2020. 8. 11.
[BOJ] 백준 1011번: Fly me to the Alpha Centauri https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행�� www.acmicpc.net x 지점에서 출발하여 y 지점으로 가는데 이전에 k번 건너뛰었다면 다음번엔 k-1번 k번 k+1 번 건너 뛸 수 있을때 x에서 y로 가는데 최소 점프수를 구하는 문제입니다. 다만 마지막 y 지점에 도착할 땐 반드시 1번 뛰어야 합니다. 만약 내가 x에서 y로 갈때 최소 점프수로 가고 싶다면 점프할때 k를 1씩 늘리거나 유지하다가 어느 시점에서 부터 .. 2020. 8. 11.
[BOJ] 백준 1007번: 벡터 매칭 https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net N개의 좌표점이 주어지고 (N은 짝수) N/2개의 벡터를 만들 때, 모든 벡터의 합이 최소가 되는 크기를 구하는 문제입니다. 20개의 벡터 쌍을 구하는 경우의 수는 20C2 + 18C2 +...+ 4C2 + 2C2 이므로 20! / 2^10 으로 다른 방법을 찾아봐야겠습니다. 2,432,902,008,176,640,000 / 1024 = 2,375,880,867,360,000 위의 벡터의.. 2020. 8. 11.
[BOJ] 백준 1004번: 어린 왕자 https://www.acmicpc.net/problem/1004 1004번: 어린 왕자 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주�� www.acmicpc.net 점과 원사이 관계로 푸는 문제. 출발 지점과 도착 지점이 주어진 원에 대하여 두 점이 모두 원 안쪽에 속하는지, 둘다 속하지 않은 경우 해당 원을 진입하거나 이탈 할 필요가 없습니다. 어느 한 지점만 속한 경우 반드시 진입 또는 이탈을 해야하므로 이 경우에만 1 증가 시켜주면 됩니다. #include #include using namespace std; typedef long l.. 2020. 8. 11.

티스토리툴바