[ 백준 3273 : 두 수의 합 ]
이번 주 토요일 ICPC인터넷 예선이 있어서 조금 급하게 닥치는대로 눈에 보이는 문제들을 푸는중...
근데 어려운건 좀 풀기가 부담스러워서 ㅋㅋㅋㅋㅋ쉬운것들만 한번 올려야..지..
수열의 크기가 주어지고 수열 그리고 한 정수가 주어진다. 그리고 조건을 만족하는 쌍의 개수를 출력하는 문제
조건은 두개의 수를 더해서 입력으로 주어진 정수가 되는것이다.
일단 N의 크기가 50만이고 만약 한개씩 대입해서 본다고 해도 최악에 50!이라는 범위가 나와버린다.
그래서 NlogN 으로 풀었는데 먼저 정렬을 한다.
그리고 한 숫자를 기준으로 그다음 인덱스를 Left 수열 크기-1를 Right 로 잡고 이분탐색으로 일치하는 쌍이 나올때마다 출력변수+1씩해준다.
그럼 총
logN + NlogN이므로 제한시간안에 충분히 들어올 수 있당.
-
[ 백준 2528 : 사다리 ] 시뮬레이션문제 시뮬레이션이나 구현 문제의 차이점을 잘 모르겠다. 나는 시간이나 상황에따라 계속 변하는 것을 구현 하는것은 시뮬레이션이라 하고 딱 멈춰진 시간, 상황에 맞는 답을 구하는 것은 구현이라고 생각하... -
[ 백준 1389 : 케빈 베이컨의 6단계 법칙 ] 한 지점을 기준으로 목표점에 얼마나 많은 간선을 지날 수 있는지를 묻는다. 그리고 그 수의 합이 가장 작은 기준 지점이 어떤 점인지를 묻는 문제이다. N이 100이다. 1을 기준으로 하고 ...
-
[ 백준 1806 : 부분합 ] 간만에 손도 풀고 감도 익힐겸 사이트에 들어갔는데 그냥 먼저 보이는 문제 하나 집어서 풀었다. 이 문제를 처음 읽고 메모이제이션해놓으면 편할것 같은데.. 생각하고 일단 바로 메모를 해놨다. DP라는 배열에 현재까...
댓글 없음:
댓글 쓰기