IT/BOJ117 백준(BOJ) 14746 Closest Pair * # 아이디어의 차이?.....아이디어는 간단한데 왜 이 생각이 늦게 떠올랐을까...아이디어를 간단하게 설명하면 다음과 같이 a와 b색의 점들이 일렬로 정렬되어있을때, a와 b색의 점 사이의 최소 거리는 결국 양옆의 점의 색이 다른경우만 확인하면 된다.a1 a2 b1 b2 a3 b3 a4 a5 b4 # 실수 했던 점아이디어 떠올리기전에 손부터 움직이다가.배열도 만들고 별 짓을 다했다... #include #include #include #include #include #include #include #include #include #define MAX 1000005 #define INF 987654321 #define MOD 1000000 #pragma warning(disable:4996) using n.. 2018. 8. 8. 백준(BOJ) 1097 마법단어 ** # kmp우선 문제 지문 읽기가 헬오브 헬...간단하게 생각하면 1~n까지의 문자열의 순열(T(0))이 i번째 부터 시작했을때 T(0)과 같은 갯수가 k개인 경우를 세주는 거다.ex) n=3, AB,RAAB,RA 문자열 주어진 경우 ABRAABRAABRARAABRAABABRARAABRAABRAABRAABRARAABAB 다음과 같이 6개의 경우가 나오게 된다.여기서 하나의 순열(ABRAABRA)을 보게된다면.ABRAABRAABRAABRAABRAABRA ABRAABRA총 i가 2가 되고, i==k 이기 떄문에 마법의 단어가 된다. 이런 순열이 총 3개가 된다. 문자열 순열에는 몇가지 규칙이있다.1234, 2341, 3412, 4123 이렇게 돌려서 동일한 순열이 되는경우 동일한 i개를 가지게 된다.(즉, 하.. 2018. 8. 1. 백준(BOJ) 15897 잘못 구현한 에라토스테네스의 체 # 수학 직접 몇개 쓰다보면 규칙이 보인다!~ #include #include #include #include #include #include #include #include #include #define MAX 3005 #define INF 987654321 #define MOD 1000000 #pragma warning(disable:4996) using namespace std; typedef long long ll; typedef pair pi; ll n,cur=1,ans=0; ll fun(ll a) { ll val=(n-1)/a,next; if(val==0) next=n; else next=(n-1)/val; ll ret=(val+1)*(next-a+1); cur=next; return ret;.. 2018. 7. 31. 백준(BOJ) 1854 k번째 최단경로 # 다익스트라 # priority queue 기본적인 다익스트라 알고리즘에서는 1에서 출발하여 i도시 까지 도착한 최단거리 하나만 저장하면 되지만,이 문제는 조금 응용하여 버려지는 거리(최단 거리가 아닌)값 들도 나중에 사용될 수 있기 때문에 저장한다. 즉, update부분에서 모든 경로의 거리에 대해서 저장해야한다.저장할때 매 k번쨰 최단거리 즉 가장 최소값만 알면되기 때문에 priority_queue를 이용한다. # 실수 했던 점순환을 할 수 있다는 것을 생각하지 못했다.(4% 쯤에서 터짐^^) #include #include #include #include #include #include #include #include #include #include #define MAX 1005 #define I.. 2018. 7. 31. 이전 1 ··· 8 9 10 11 12 13 14 ··· 30 다음