#문제

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

 

1051번: 숫자 정사각형

N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

www.acmicpc.net

 

#작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
using namespace std;
 
int n, m;
char board[51][51];
int main(){
    cin>>n>>m;
    
    for(int i=0; i<n; i++){
        cin>>board[i];
    }
    
    int size_max = min(n, m);
    
    int result = 0;
    for(int size=0; size<size_max; size++){
        for(int i=0; i<n-size; i++){
            for(int j=0; j<m-size; j++){
                if(board[i][j]==board[i+size][j])
                    if(board[i][j]==board[i][j+size])
                        if(board[i][j]==board[i+size][j+size])
                            result = max(result, size+1);
            }
        }
    }
    
    cout<<result*result;
    return 0;
}
 cs

##

너무 오랜만에 문제를 풀었다... 다시 기본부터

실수 1. 최대 입력 가능한 n, m의 크기가 50이므로 배열을 [51][51]으로 선언해야함.

실수 2. 1x1사이즈의 정사각형이 만들어질 수 있음을 간과함.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 10552번 :: DOM  (0) 2020.02.25
BOJ 2468번 :: 안전영역  (0) 2020.02.22
BOJ 11403번 :: 경로 찾기  (0) 2020.02.21
BOJ 10026번 :: 적록색약  (0) 2020.02.16
BOJ 2583번 :: 영역 구하기  (0) 2020.02.13

https://www.codingame.com/training/easy/lumen

 

Practice Loops and 2D array with the exercise "Lumen"

Want to practice Loops and 2D array? Try to solve the coding challenge "Lumen".

www.codingame.com

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import sys
import math
 
n = int(input())
l = int(input())
line = [[''for i in range(n)]for j in range(n)]
for i in range(n):
    line[i] = input().split()
 
for i in range(n):
    for j in range(n):
        if line[i][j]=='C':
            for x in range(-(l-1), l):
                for y in range(-(l-1), l):
                    if i+x<0 or i+x>=n or j+y<0 or j+y>=n or line[i+x][j+y]=='C':
                        continue
                    line[i+x][j+y] = 'O'
 
count=0
for i in range(n):
    for j in range(n):
        if line[i][j]=='X':
            count = count+1
print(count)
 cs
저작자표시 비영리

'python > codinGame' 카테고리의 다른 글

GRAFFITI ON THE FENCE  (0) 2020.03.06
Rectangle Partition  (0) 2020.03.06
Defibrillators  (0) 2020.03.03
ANEO Sponsored Puzzle  (0) 2020.03.03

https://www.codingame.com/training/easy/graffiti-on-the-fence

 

Practice Array forbidden with the exercise "Graffiti on the fence"

Want to practice coding? Try to solve this easy puzzle "Graffiti on the fence" (25+ languages supported).

www.codingame.com

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import sys
import math
 
# Auto-generated code below aims at helping you parse
# the standard input according to the problem statement.
 
l = int(input())
n = int(input())
 
fill = [[0 for i in range(2)]for j in range(n)]
 
for i in range(n):
    fill[i][0], fill[i][1] = [int(j) for j in input().split()]
        
fill.sort()     # st점을 기준으로 오름차순 정렬된다.
 
# 칠해지지않은 구간 시작지점, 끝지점 초기화.
start = 0
end = start+1
# 칠해지지 않은 구간을 찾아서 프린트한다.
for f in range(n+1):
    if f==n:                        # 주어진 칠해진 구간 모두 탐색 후 담벼락의 끝까지 탐색.
        if start!=l:                # 마지막 칠해진 구간 ~ 담벼락 끝까지 빈 벽이 있음.
            print(start, end=" ")
            print(l)
        if start==l and end==1:     # end==1은 초기 end 값에서 한번도 갱신된 적 없음을 뜻한다.
            print("All painted")
    # f번째 칠해진 구간 직전에 칠해지지 않은 구간이 존재함.
    elif fill[f][0]>start:
        print(start, end=" ")
        end = fill[f][0]
        print(end)
        start = fill[f][1]  # f번째 칠해진 구간 끝점에서 칠해지지않은 구간 재탐색.
    # f번째 칠해진 구간 내부에 현재 칠해지지않은 구간 위치가 포함됨.
    elif fill[f][0]<=start:
        # 현재 칠해지지 않은 구간 위치와 f번째 칠해진 구간 끝 지점 중 더 큰 것을 선택.
        start = max(start, fill[f][1])
cs

저작자표시 비영리

'python > codinGame' 카테고리의 다른 글

LUMEN  (0) 2020.03.06
Rectangle Partition  (0) 2020.03.06
Defibrillators  (0) 2020.03.03
ANEO Sponsored Puzzle  (0) 2020.03.03

https://www.codingame.com/training/easy/rectangle-partition

 

Practice Loops and Arrays with the exercise "Rectangle Partition"

Want to practice Loops and arrays? Try to solve the coding challenge "Rectangle Partition".

www.codingame.com

import sys
import math

w, h, count_x, count_y = [int(i) for i in input().split()]
x = ['']*(count_x)
y = ['']*(count_y)

# x축, y축을 나누는 숫자 입력
tmp = 0
for i in input().split():
    x[tmp] = int(i)
    tmp +=1
tmp = 0
for i in input().split():
    y[tmp] = int(i)
    tmp = tmp+1
    
# x와 y리스트를 각각 set으로 변환 후 list로 재변환해서 중복되는 데이터를 제거한다.
x = list(set(x))
x.sort()
y = list(set(y))
y.sort()

count =0        # 정사각형의 개수 0으로 초기화.

# 리스트 x와 y의 길이 미리 계산하여 저장해둔다.
lx = len(x)
ly = len(y)

dpx = [int(0)]*(w+1)
dpy = [int(0)]*(h+1)

for x_s in range(lx):
    for x_inc in range(x_s, lx+1):
        if x_inc==x_s:    # 건너뛰는 간격이 0이면 본인.
            dpx[ x[x_s] ] +=1
        elif x_inc==lx:
            dpx[ w-x[x_s] ] +=1  # 제일 끝으로 가면 전체 길이에서 본인 뺀다.
        else:           # 건너뛰는 간격 크기만큼 간 후 본인과 뺀다.
            dpx[x[x_inc]-x[x_s]] +=1
dpx[w] = 1

for y_s in range(ly):  
    for y_inc in range(y_s, ly+1):
        if y_inc==y_s:
            dpy[ y[y_s] ] +=1
        elif y_inc==ly:
            dpy[ h-y[y_s] ] +=1
        else:
            dpy[ y[y_inc]-y[y_s] ] +=1
dpy[h] = 1 

#print(dpx)
#print(dpy)

for i in range(w+1):
    for j in range(h+1):
        if dpx[i]==0 or dpy[j]==0:
            continue
        if i==j:
            #print(i, j, dpx[i], dpx[j], dpx[i]*dpy[j])
            count += dpx[i]*dpy[j]
            
print(count)
import sys
import math

w, h, count_x, count_y = [int(i) for i in input().split()]
x = ['']*(count_x)
y = ['']*(count_y)

# x축, y축을 나누는 숫자 입력
tmp = 0
for i in input().split():
    x[tmp] = int(i)
    tmp +=1
tmp = 0
for i in input().split():
    y[tmp] = int(i)
    tmp = tmp+1
    
# x와 y리스트를 각각 set으로 변환 후 list로 재변환해서 중복되는 데이터를 제거한다.
x = list(set(x))
x.sort()
y = list(set(y))
y.sort()

count =0        # 정사각형의 개수 0으로 초기화.

x_diff=0
y_diff=0

# 리스트 x와 y의 길이 미리 계산하여 저장해둔다.
lx = len(x)
ly = len(y)

for x_s in range(lx+1):
    for y_s in range(ly+1):
        for x_inc in range(lx-x_s+1):
            if x_inc==0 and x_s!=lx:    # 건너뛰는 간격이 0이면 본인.
                x_diff = x[x_s]
            elif x_inc==lx-x_s and x_s==lx:
                x_diff = w
            elif x_inc==lx-x_s:
                x_diff = w-x[x_s]   # 제일 끝으로 가면 전체 길이에서 본인 뺀다.
            else:           # 건너뛰는 간격 크기만큼 간 후 본인과 뺀다.
                x_diff = x[x_s+x_inc]-x[x_s]
                
            for y_inc in range(ly-y_s+1):
                if y_inc==0 and y_s!=ly:
                    y_diff = y[y_s]
                elif y_inc==ly-y_s and y_s==ly:
                    y_diff = h
                elif y_inc==ly-y_s:
                    y_diff = h-y[y_s]
                else:
                    y_diff = y[y_s+y_inc]-y[y_s]
                #print("x_s: "+str(x_s)+" x_inc: "+str(x_inc)+" y_s: "+ str(y_s)+" y_inc: "+str(y_inc))
                #print(str(x_diff)+" "+str(y_diff), end="\n")
                # 두 간격이 같고, 0이 아니면 count 추가.    
                if x_diff==y_diff and x_diff!=0:
                    count = count+1

print(count)

첫 번째 코드는 hi-density는 물론, low-density case를 통과하지 못한다.

두 번째 코드는 hi-density만 통과하지 못한다...

이미 계산한 정보는 저장하래서 저장했는데 뭐가 문제일까?

 

import sys
import math

w, h, count_x, count_y = [int(i) for i in input().split()]
x = ['']*(count_x)
y = ['']*(count_y)

# x축, y축을 나누는 숫자 입력
tmp = 0
for i in input().split():
    x[tmp] = int(i)
    tmp +=1
tmp = 0
for i in input().split():
    y[tmp] = int(i)
    tmp = tmp+1
    
# x와 y리스트를 각각 set으로 변환 후 list로 재변환해서 중복되는 데이터를 제거한다.
x = list(set(x))
x.sort()
y = list(set(y))
y.sort()

count =0        # 정사각형의 개수 0으로 초기화.

x_diff=0
y_diff=0

# 리스트 x와 y의 길이 미리 계산하여 저장해둔다.
lx = len(x)
ly = len(y)

dpx = []
dpy = []

for x_s in range(lx):
    for x_inc in range(x_s, lx+1):
        if x_inc==x_s:    # 건너뛰는 간격이 0이면 본인.
            dpx.append(x[x_s])
        elif x_inc==lx:
            dpx.append(w-x[x_s])   # 제일 끝으로 가면 전체 길이에서 본인 뺀다.
        else:           # 건너뛰는 간격 크기만큼 간 후 본인과 뺀다.
            dpx.append(x[x_inc]-x[x_s])
dpx.append(w)

for y_s in range(ly):  
    for y_inc in range(y_s, ly+1):
        if y_inc==y_s:
            dpy.append(y[y_s])
        elif y_inc==ly:
            dpy.append(h-y[y_s])
        else:
            dpy.append(y[y_inc]-y[y_s])
dpy.append(h)    

# dpx와 dpy를 정렬한다.
dpx.sort()
dpy.sort()

for i in range(len(dpx)):
    for j in range(len(dpy)):
        if dpx[i]==dpy[j]:
            count = count+1
            
print(count)

부분 선분의 길이를 인덱스로 하는 배열에 부분 선분이 몇 개 등장하는지 저장하여 나중에 x기준, y기준으로 같은 길이의 선분이 있으면 배열의 값만 곱해서 더해주면 되는 코드이다.

이 코드는 hi-density만 통과하지 못한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import sys
import math
 
w, h, count_x, count_y = [int(i) for i in input().split()]
x = []
y = []
 
# x축, y축을 나누는 숫자 입력
for i in input().split():
    x.append(int(i))
for i in input().split():
    y.append(int(i))
 
# x와 y의 부분 선분 리스트에 시작점 0과 끝점 w/h를 추가한다.
x.append(0)
x.append(w)
y.append(0)
y.append(h)
 
# x와 y리스트를 각각 set으로 변환 후 list로 재변환해서 중복되는 데이터를 제거한다.
x = list(set(x))
y = list(set(y))
x.sort()
y.sort()
 
count =0        # 정사각형의 개수 0으로 초기화.
 
# 리스트 x와 y의 길이 미리 계산하여 저장해둔다.
lx = len(x)
ly = len(y)
 
dpx = {}
dpy = {}
 
for x_s in range(lx):
    for x_inc in range(x_s+1, lx):
        xkey = x[x_inc]-x[x_s]
            
        if xkey in dpx:
            dpx[xkey] += 1
        else:
            dpx[xkey] =1
 
 
for y_s in range(ly):  
    for y_inc in range(y_s+1, ly):
        ykey = y[y_inc]-y[y_s]
            
        if ykey in dpy:
            dpy[ykey] += 1
        else:
            dpy[ykey] =1
 
for i in dpx.keys():
    for j in dpy.keys():
        if i==j:
            count += dpx[i]*dpy[j]
print(count)
 cs

딕셔너리 자료형을 사용해서, 키로 사용할 부분 선분의 길이가 딕셔너리에 존재하면 value를 1 증가, 아니면 딕셔너리에 추가하는 방식을 사용했더니 hi-density를 하나 통과할 수 있었다.

=>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import sys
import math
 
w, h, count_x, count_y = [int(i) for i in input().split()]
 
# x축, y축을 나누는 숫자 입력
x = [int(i) for i in input().split()]
y = [int(i) for i in input().split()]
 
# x와 y의 부분 선분 리스트에 시작점 0과 끝점 w/h를 추가한다.
x.append(0)
x.append(w)
y.append(0)
y.append(h)
 
# x와 y리스트를 각각 set으로 변환 후 list로 재변환해서 중복되는 데이터를 제거한다.
x = list(set(x))
y = list(set(y))
x.sort()
y.sort()
 
count =0        # 정사각형의 개수 0으로 초기화.
 
# 리스트 x와 y의 길이 미리 계산하여 저장해둔다.
lx = len(x)
ly = len(y)
 
dpx = {}
dpy = {}
 
for x_s in range(lx-1):
    for x_inc in range(x_s+1, lx):
        xkey = x[x_inc]-x[x_s]
            
        if xkey in dpx:
            dpx[xkey] += 1
        else:
            dpx[xkey] =1
 
 
for y_s in range(ly-1):  
    for y_inc in range(y_s+1, ly):
        ykey = y[y_inc]-y[y_s]
            
        if ykey in dpy:
            dpy[ykey] += 1
        else:
            dpy[ykey] =1
 
for i in dpx.keys():
    if i in dpy:
        count+=dpx[i]*dpy[i]
print(count)
 cs

직전의 코드와 다른 점은,

dpx에 존재하는 각각의 키 i가 dpy에 존재하는지 여부만 검사하여 dpx[i]*dpy[i]를 수행했다는 점이다.(line 50~52)

모든 케이스를 통과하였다!

저작자표시 비영리

'python > codinGame' 카테고리의 다른 글

LUMEN  (0) 2020.03.06
GRAFFITI ON THE FENCE  (0) 2020.03.06
Defibrillators  (0) 2020.03.03
ANEO Sponsored Puzzle  (0) 2020.03.03

https://www.codingame.com/training/easy/defibrillators

 

Practice Loops and Distances with the exercise "Defibrillators"

Want to practice Loops and distances? Try to solve the coding challenge "Defibrillators".

www.codingame.com

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import sys
import math
 
# Auto-generated code below aims at helping you parse
# the standard input according to the problem statement.
 
lon = input().split(',')
lon = lon[0]+"."+lon[1]
lat = input().split(',')
lat = lat[0]+"."+lat[1]
n = int(input())
defib = ['']*n
for i in range(n):
    defib[i] = input().split(';')
    defib[i][4] = defib[i][4].split(',')
    defib[i][4] = defib[i][4][0]+"."+defib[i][4][1]
    defib[i][5] = defib[i][5].split(',')
    defib[i][5] = defib[i][5][0]+"."+defib[i][5][1]
    
 
minD = float(1000000000000000000000) # 최소거리.
minI = 0        # 최소거리를 가지는 defib의 인덱스.
 
for i in range(n):
    x = (math.radians(float(defib[i][4]))-math.radians(float(lon)))*
math.cos((math.radians(float(lat))+math.radians(float(defib[i][5])))/2)
    y = (math.radians(float(defib[i][5]))-math.radians(float(lat)))
    d = math.sqrt(x**2 + y**2)*6371
    if float(minD) > d:
        minD = d
        minI = i
# Write an action using print
# To debug: print("Debug messages...", file=sys.stderr)
 
print(defib[minI][1])
 cs

lat = input() 형식으로 입력받으면 43,50982가 스트링 형식으로 입력된다.
43.50982의 실수 형태로 변환해가며 입력받기 위해서는
lat = float(input().replace(",", "."))으로 입력받아야한다.
위의 문제에서 사용하기 위해서는 라디안으로 변환해야하므로
lat = math.radians(lat)으로 변환해준다.

내가 사용했던

lat = input().split(",")
lat = lat[0]+"."+lat[1]
lat = float(lat)

위의 코드에 비하면 아주 간단하게 변환할 수 있다!

 

+) 파이썬에서 cos 함수와 sqrt함수는 math.cos(), math.sqrt()로 사용한다.

저작자표시 비영리

'python > codinGame' 카테고리의 다른 글

LUMEN  (0) 2020.03.06
GRAFFITI ON THE FENCE  (0) 2020.03.06
Rectangle Partition  (0) 2020.03.06
ANEO Sponsored Puzzle  (0) 2020.03.03

+ Recent posts

티스토리툴바