algorithm/problem solving

acmicpc.net 1292번 쉽게 푸는 문제, 1269번 대칭 차집합

qkqhxla1 2016. 7. 10. 14:44

https://www.acmicpc.net/problem/1292


1292번 쉽게 푸는 문제.


문제

동호는 내년에 초등학교를 입학한다. 그래서 동호 어머니는 수학 선행 학습을 위해 쉽게 푸는 문제를 동호에게 주었다.


이 문제는 다음과 같다. 1을 한 번, 2를 두 번, 3을 세 번, 이런 식으로 1 2 2 3 3 3 4 4 4 4 5 .. 이러한 수열을 만들고 어느 일정한 구간을 주면 그 구간의 합을 구하는 것이다.


하지만 동호는 현재 더 어려운 문제를 푸느라 바쁘기에 우리가 동호를 도와주자.


입력

첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1≤A≤B≤1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다.


출력

첫 줄에 구간에 속하는 숫자의 합을 출력한다.


예제 입력  

3 7

예제 출력  

15


파이썬 소스. c++로 짜도 비슷할거 같아서 굳이 적지는 않음.

n,m = map(int,raw_input().split())
num_list = []
g = 1
for i in range(1,50):
    num_list.append([g,i])
    g += i

s = 0
for i in range(n,m+1):
    for j in range(len(num_list)):
        if i >= num_list[j][0] and i < num_list[j+1][0]:
            s += num_list[j][1]
            break
print s

https://www.acmicpc.net/problem/1269


1269번 대칭 차집합


문제

자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 이 때, 두 집합의 대칭 차집합의 원소의 개수를 출력하는 프로그램을 작성하시오. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 한다.


예를 들어, A = { 1, 2, 4 } 이고, B = { 2, 3, 4, 5, 6 } 라고 할 때,  A-B = { 1 } 이고, B-A = { 3, 5, 6 } 이므로, 대칭 차집합의 원소의 개수는 1 + 3 = 4개이다.


입력

첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어진다. 각 집합의 원소의 개수는 200,000을 넘지 않으며, 모든 원소의 값은 100,000,000을 넘지 않는다.


출력

첫째 줄에 대칭 차집합의 원소의 개수를 출력한다.


예제 입력  

3 5

1 2 4

2 3 4 5 6

예제 출력  

4


파이썬 소스.

raw_input()
sets = [map(int,raw_input().split()) for i in range(2)]
common = len(list(set(sets[0]).intersection(sets[1])))
print len(sets[0])+len(sets[1])-2*common